[백준] 1260번: DFS와 BFS

2024. 9. 29. 01:03·PS

 

 

 


 

문제

https://www.acmicpc.net/problem/1260

 

 

개념

그래프, DFS, BFS

 

 

실행 결과

 

 

 

 

 

구현 코드(c++)

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<vector<int>> graph;  // 2차원 벡터로 선언
vector<bool> visited; // 방문 처리용 배열 선언

// 깊이 우선 탐색: 스택 재귀
void dfs(int x) {
  visited[x] = true;
  cout << x << " ";

  // 방문하지 않은 노드라면 재귀 반복
  for (int i = 0; i < graph[x].size(); i++) {
    int y = graph[x][i];
    if (!visited[y])
      dfs(y);
  }
}

// 너비 우선 탐색: 큐
void bfs(int start) {
  queue<int> q;
  visited[start] = true; // 현재 노드 방문 처리
  q.push(start); // 넣기

  while (!q.empty()) {
    int x = q.front(); // 가장 먼저 들어온 원소 확인
    q.pop(); // 꺼내기 
    cout << x << " ";

    for (int i = 0; i < graph[x].size(); i++) {
      int y = graph[x][i];
      if (!visited[y]) {
        visited[y] = true; 
        q.push(y);
      }
    }
  }
}

int main() {
  int n, m, v;
  cin >> n >> m >> v;

  // 그래프 및 방문 정보 초기화
  graph.resize(n + 1);
  visited.resize(n + 1, false);

  // 간선을 입력받아 그래프에 추가
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }

  // 인접 리스트 정렬 (정점 번호가 작은 것부터 방문하기 위해)
  for (int i = 1; i <= n; i++) {
    sort(graph[i].begin(), graph[i].end());
  }

  // DFS
  dfs(v);
  cout << endl;

  // visited 배열 초기화
  fill(visited.begin(), visited.end(), false);

  // BFS
  bfs(v);
  cout << endl;

  return 0;
}

 

 

 

 

코드 설명

 

먼저 이 문제를 풀기 위해서는 그래프 자료구조를 복습해야 한다.

또한 기본적으로 스택과 큐에 대한 이해가 있어야 한다.

 

💛 DFS - 깊이 우선 탐색

스택 or 재귀 함수를 이용하여 구현한다.

동작과정

  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  3. 더이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

💛 BFS - 너비 우선 탐색

그래프에서 가까운 노드부터 우선적으로 탐색한다. 죽, 가까운 거리 순이라고 생각하면 된다.

큐를 이용하며 구현하며 주로 최단경로를 찾는 문제(간선 길이 동일한 경우)에 활용된다.

동작과정

  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
  2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.
  3. 더이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

 

 

 

먼저 그래프를 2차원 배열로 선언하여 노드와 방문 정보를 받을 수 있게 한다.

그래프 탐색을 위해서는 방문 처리가 필요하기 때문이다.

dfs는 루트 노드부터 내려가면서 방문을 반복하는 단순한 구조이다.

이에 반해 bfs는 약간 복잡하고 느껴질 수도 잇는데

거리 순으로 큐에서 빼낸다고 생각하면 이해하기 좀 더 쉽다.

 

main에서는  노드 번호를 인덱스와 일치 시키기 위해 n+1의 크기로 초기화했다.

resize 함수로 크기를 재할당하는 이유는 필요 없이 메모리가 재할당되는 것을 방지하기 위함이다. 

dfs를 하고 나서는 algorithm 헤더에 정의되어 있는 fill 함수를 통해 방문 여부를 초기화할 수 있다.

 

 


 

STL 관련하여 더 자세한 내용은 아래 블로그를 참조할 수 있다.

 

[C/C++] resize() vs reserve()

앞선 string 정리 글에서 resize(); 와 reserve(); 차이에 대해서 간단히 언급했다. 좀 더 상세히 정리하고 머리에 새겨놓고 싶어서 따로 글을 정리해 올린다.앞서 설명한 것 처럼 배열이나 문자열, 벡터

velog.io

 

 

[C++] 배열 초기화, 벡터 초기화, fill 함수

C++에서 배열을 선언하고 초기화를 해주지 않으면 배열은 쓰레기 값으로 채워져있다. 아래의 코드를 실행해보면 #include using namespace std; int main() { int arr[5]; for (int i = 0; i < 5; i++) { cout

breakcoding.tistory.com

 

저작자표시 (새창열림)

'PS' 카테고리의 다른 글

[백준] 2178번: 미로 탐색  (5) 2024.10.01
[코드트리] 행복한 수열의 개수  (1) 2024.09.29
[백준] 1475번: 방 번호  (0) 2024.09.25
[백준] 5585번: 거스름돈  (0) 2024.09.24
[백준] 11407번: 동전 0  (0) 2024.09.24
'PS' 카테고리의 다른 글
  • [백준] 2178번: 미로 탐색
  • [코드트리] 행복한 수열의 개수
  • [백준] 1475번: 방 번호
  • [백준] 5585번: 거스름돈
abyss-s
abyss-s
프론트엔드 개발합니다!
  • abyss-s
    abyss-s의 블로그입니다.
    abyss-s
  • 전체
    오늘
    어제
    • 분류 전체보기 (192)
      • Web (16)
        • JavaScript (6)
        • TypeScript (1)
        • React (5)
        • Vue (0)
        • Storybook (1)
        • Next.js (1)
      • Backend & Infra (8)
        • Database (3)
        • Node.js (2)
        • SpringBoot (1)
      • PS (71)
      • CS (30)
        • OS (13)
        • Structure & Algorithm (5)
        • Network (10)
        • 정보처리기사 (2)
      • Language (18)
        • OOP (1)
        • JAVA (13)
        • C++ (4)
      • Activities (16)
        • 멋쟁이 사자처럼 (2)
        • OSSCA (3)
        • LG U+ URECA (5)
        • Project (2)
        • Conference (1)
      • IT (3)
      • AI (0)
      • Git & Github (5)
      • Notion (1)
      • Statistics (11)
      • Book (5)
      • Diary (1)
      • Game (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

    • 깃허브
    • 백준
    • 트위터
  • 공지사항

    • abyss-s의 티스토리에 오신 것을 환영합니다.
  • 인기 글

  • 태그

    github
    Python
    파이썬
    React
    백준
    생활코딩
    Java
    네트워크
    BFS
    그리디
    DP
    C++
    OS
    운영체제
    자바스크립트
    BAEKJOON
    자바기반응용프로그래밍
    통계학
    JavaScript
    코드트리
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
abyss-s
[백준] 1260번: DFS와 BFS
상단으로

티스토리툴바