[백준] 1260번: DFS와 BFS

 

 

 

---

 

문제

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()

 

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