[백준 1260번] DFS와 BFS

1260번: DFS와 BFS

 

DFS(Depth-First-Search)는 깊이 우선 탐색, BFS(Breadth-First-Search)는 너비 우선 탐색으로, 정점과 간선을 잇는 그래프 자료구조를 이용한 탐색 기법이다. 코드와 테스트 케이스를 통해 알고리즘을 파악하자.

 

그래프(정점 7개와 간선 7개)

 

위의 그래프 구조는 1에서 7까지의 정점 7개와 이들을 잇는 간선 7개로 이루어져있다. 이와 같이, 문제 내에서는 그래프 구조에 대한 기본적인 정보(정점 N개, 간선 M개, 시작점 V)를 제공한다. 따라서 다음과 같이 N, M, V를 입력 받고 M개의 간선에 대한 연결 정점의 정보를 이중벡터 graph에 저장한다. 

 

int N, M, V;
scanf("%d %d %d", &N, &M, &V);

vector<vector<int>> graph(N+1, vector<int>(0));
for (int i=0; i<M; i++) {
  int n1, n2;
  scanf("%d %d", &n1, &n2);

  graph[n1].push_back(n2);
  graph[n2].push_back(n1);
}

for (int i=1; i<=N; i++)
    sort(graph[i].begin(), graph[i].end());

 

예를 들어, N=7, M=7, V=1 일 때, M개의 간선에 대한 정보가 다음과 같이 주어지면

 

1 3
1 2
1 5
2 5
3 4
3 6
2 7

 

graph에는 다음과 같이 정보가 저장된다. 문제 내에서 정점을 순환할 때 값이 작은 정점 먼저 순환한다고 했으므로, graph[] 의 값들은 정렬하여 저장한다.

 

//graph[정점]: 정점과 연결되어있는 다른 정점의 목록

graph[1] 2 3 5
graph[2] 1 5 7 
graph[3] 1 4 6 
graph[4] 3 
graph[5] 1 2
graph[6] 3
graph[7] 2

 

이렇게 입력된 정보를 셋팅 했다면 DFS와 BFS 알고리즘을 쓸 준비가 완료된 것이다. 

 

먼저, DFS를 통해 모든 정점들을 탐색해보자.  DFS 알고리즘은 수직의 방향으로 그래프를 따라가 세로 방향의 모든 정점을 탐색한 후 다음 분기(branch)를 탐색 하는 방법이다. 다음의 그림에서 1은 2, 3, 5 분기 중 하나로 이동할 수 있다. 문제에서는 여러 정점으로 이동 가능한 경우 숫자가 작은 정점 먼저 탐색하라고 했으므로, 2번 정점으로 탐색을 이동한다. 2번 정점은 두가지 분기(branch)를 가지고 있고, 5번과 7번 정점으로 이동 가능하다. 이 때 7은 잠시 제쳐두고, 5번으로 탐색을 이동한다. 5번 정점은 2번과 1번으로 이동 가능하지만, 이 둘 정점은 이미 지나왔기 때문에 5번 정점에서는 더이상 나아갈 정점이 없다. 이렇게 1->2->5 순으로 하나의 줄기를 모두 탐색하였을 때, 2번 분기로 다시 돌아와 제쳐둔 7로 이동한다. 이렇게 미로와 같이 앞을 향해 나아가다가, 막혔을 때 다시 이전 갈림길로 돌아와 다른 갈림길로 가는 형태의 탐색을 깊이 우선 탐색이라 이해하면 된다.

 

DFS 탐색 순서

 

깊이 우선 탐색은 재귀로 구현 가능하다.

 

void dfs(vector<vector<int>> graph, vector<bool>& check, int start) {

    printf("%d ", start);
    check[start] = true;

    for (int i=0; i<graph[start].size(); i++) {
        
        int next = graph[start][i];
        if (check[next]) continue;
        dfs(graph, check, next);
    }
}

 

start(현재 정점)에서 이동할 수 있는 정점은 graph[start]에 저장되어있으므로, 이들 목록 중에서 아직 탐색한 적이 없는(check[next] == false) 정점을 다시 시작점으로 하여 탐색한다. 점점 수직으로 내려가면서 더이상 탐색할 것이 없을 때, 이전 정점으로 돌아와 제쳐두었던 graph[start]의 다른 정점들을 탐색한다. 

 

다음으로, BFS를 통해 정점을 탐색해보자. BSF는 먼저 같은 선상에 있는 분기를 모두 탐색하고 그 다음 분기로 이동하는 방법이다. 먼저 1의 경우 2, 3, 5의 정점으로 이동 가능하다. 따라서 같은 가로 선상에 있는 2, 3, 5를 먼저 탐색한다. 이후, 2를 따라 내려가면 5와 7로 이동 가능하고 3을 따라 내려가면 4와 6으로 이동 가능한데, 이 때 5는 이전에 탐색한 이력이 있으므로 5를 제외한 4, 6, 7을 탐색한다. 이렇게 1 -> 2, 3, 5 -> 4, 6, 7 순서로 탐색하는 방법을 BFS 너비 우선 탐색이라 한다.

 

BFS 탐색 순서

 

BFS는 큐(queue)를 이용하여 구현할 수 있다. 먼저 첫번째 분기 라인에 있는 start를 큐에 넣는다. 이 때 tmp=q.font()인 start에서 이동할 수 있는 모든 정점은 graph[tmp]에 저장되어있다. 이동할 수 있는 정점 중 아직 탐색하지 않은 정점만을 큐에 저장하고, 이전 라인에 있던 tmp는 큐에서 삭제한다. 이렇게 한 분기의 정점을 큐에 저장하고, 각각의 정점에서 이동할 수 있는 그 다음 분기의 정점들을 저장하여 전체 그래프를 모두 탐색한다.

 

void bfs(vector<vector<int>> graph, vector<bool>& check, int start) {

    queue<int> q;
    q.push(start);
    check[start] = true;
    printf("%d ", start);

    while (!q.empty()) {

        int tmp = q.front();

        for (int i=0; i<graph[tmp].size(); i++) {
            int next = graph[tmp][i];
            if (check[next]) continue;
            q.push(next);
            check[next] = true;
            printf("%d ", next);
        }
        q.pop();
    }
}

 

데이터를 입력받아 bfs와 dfs의 탐색 결과를 출력하는 전체 코드는 다음과 같다.

 

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <vector>
#include <cmath>
#include <tuple>
#include <queue>
using namespace std;

void dfs(vector<vector<int>> graph, vector<bool>& check, int start) {

    printf("%d ", start);
    check[start] = true;

    for (int i=0; i<graph[start].size(); i++) {
        
        int next = graph[start][i];
        if (check[next]) continue;
        dfs(graph, check, next);
    }
}

void bfs(vector<vector<int>> graph, vector<bool>& check, int start) {

    queue<int> q;
    q.push(start);
    check[start] = true;
    printf("%d ", start);

    while (!q.empty()) {

        int tmp = q.front();

        for (int i=0; i<graph[tmp].size(); i++) {
            int next = graph[tmp][i];
            if (check[next]) continue;
            q.push(next);
            check[next] = true;
            printf("%d ", next);
        }
        q.pop();
    }
}

int main() {

    int N, M, V;
    scanf("%d %d %d", &N, &M, &V);

    vector<vector<int>> graph(N+1, vector<int>(0));
    for (int i=0; i<M; i++) {
        int n1, n2;
        scanf("%d %d", &n1, &n2);

        graph[n1].push_back(n2);
        graph[n2].push_back(n1);
    }

    for (int i=1; i<=N; i++)
        sort(graph[i].begin(), graph[i].end());

    vector<bool> check1(N+1, false), check2(N+1, false);
    dfs(graph, check1, V); 
    printf("\n");
    bfs(graph, check2, V);
    return 0;
}