백준 1260 C++

• DFS와 BFS는 그래프와 트리의 모든 정점/노드를 방문하는 기초 알고리즘이다.
• 그래프와 트리의 차이: 둘다 노드와 간선을 가진다는 점은 같으나, 그래프에서는 트리와 달리 접점마다 간선이 존재하지 않을 수 있으며, 루트 노드와 부모 노드, 자식 노드 개념이 존재하지 않는다.
• 그래프는 인접행렬 또는 인접리스트로 구현할 수 있다. 인접행렬은 2차원행렬로 구현하여 시간복잡도가 O(V^2), 인접리스트는 vector<pair<int, int>> 형태로 구현하여 시간복잡도가 O(V+E)이다. 일반적으로 속도 개선을 위해 인접리스트를 사용하며, 인접행렬은 구현 난이도가 쉽다는 장점이 있다.
• DFS는 깊이 우선 알고리즘으로 방문한 점에서 이어지는 점이 있으면 더 이상 이어지는 점이 없을 때까지 같은 방향으로 탐색하고, 이어지는 점이 없으면 탐색을 시작한 노드에서 다른 방향으로 이동한다.
• BFS는 너비 우선 알고리즘으로 가까운 노드를 우선해서 방문한다.
• 최단경로 탐색 시 BFS를 사용하며, 그래프의 형태가 DFS에 적합한 경우에 DFS를 사용한다. 모든 경로 탐색 시에는 둘 중 어느 것을 사용해도 되지만, DFS 구현이 더 간단하다.
• DFS는 주로 재귀를 사용하여 구현하고, BFS는 주로 큐를 사용하여 구현한다.

문제에서는 하나의 그래프가 주어졌을 때 DFS로 구한 방문순서와 BFS로 구한 방문순서를 모두 출력하고자 한다. 연결된 점이 여러 개라면 오름차순으로 방문한다. => 인접행렬을 사용하면 오름차순으로 정렬되어 있으므로 추가 처리가 필요하지 않다.

예제로 주어진 그래프를 그려보면 이미지와 같다.

인접행렬/재귀/큐를 사용하여 구현하면 다음과 같다.

#include <iostream>
#include <queue>

#define MAX 1001

using namespace std;

int N, M, V;
bool graph[MAX][MAX];
bool visited[MAX];
queue<int> q;

void dfs(int V) {

    visited[V] = 1;
    cout << V << " ";

    for (int i = 1; i <= N; ++i) {
        if (graph[V][i] == 1 && visited[i] == 0) {
            dfs(i);
        }
    }
}

void bfs(int V) {
    q.push(V);
    visited[V] = 1;
    cout << V << " ";

    while (!q.empty()) {
        V = q.front();
        q.pop();

        for (int i = 1; i <= N; ++i) {
            if (graph[V][i] == 1 && visited[i] == 0) {
                q.push(i);
                visited[i] = 1;
                cout << i << " ";
            }
        }
    }

}

void reset() {
    for (int i = 1; i <= N; ++i)
    {
        visited[i] = 0;
    }
}

int main() {
    cin >> N >> M >> V;

    int a, b;

    for (int i = 0; i < M; ++i) {
        cin >> a >> b;
        graph[a][b] = 1;
        graph[b][a] = 1;
    }

    dfs(V);
    reset();
    cout << endl;
    bfs(V);

    return 0;
}

DFS 방문순서를 구한 후 visited 행렬을 초기화하여 BFS 방문순서를 구한다.

첫 번째 예제 입력으로 출력을 확인해 보자.

• DFS

  • 1번에서 시작 -> dfs(1) 실행
  • visited[1] = 1
  • graph[1][1] != 1 -> 다음 반복
  • graph[1][2] == 1 && visited[2] == 0 -> dfs(2) 실행
  • visited[2] = 1
  • graph[2][1] == 1 && visited[1] == 1 -> 다음 반복
  • graph[2][2] != 1 -> 다음 반복
  • graph[2][3] != 1 -> 다음 반복
  • graph[2][4] == 1 && visited[4] == 0 -> dfs(4) 실행
  • visited[4] = 1
  • graph[4][1] == 1 && visited[1] == 1 -> 다음 반복
  • graph[4][2] == 1 && visited[2] == 1 -> 다음 반복
  • graph[4][3] == 1 && visited[3] == 0 -> dfs(3) 실행
  • visited[3] = 1
  • graph[3][1] == 1 && visited[1] == 1 -> 다음 반복
  • graph[3][2] != 1 -> 다음 반복
  • graph[3][3] != 1 -> 다음 반복
  • graph[3][4] == 1 && visited[4] == 1 -> 다음 반복
  • N이 4이므로 더 이상 반복하지 않고, 재귀도 실행되지 않으므로 함수 실행 종료
  • 출력된 순서는 1 2 4 3

• BFS

  • 1번에서 시작 -> dfs(1) 실행
  • q.push(1) -> 현재 큐: {1}
  • visited[1] = 1
  • 큐가 비어있지 않으므로 while문 실행
    • 현재 큐의 가장 앞에 있는 원소를 V 값에 할당 -> V = 1
    • q.pop() -> 현재 큐: {}
    • graph[1][1] != 1 -> 다음 반복
    • graph[1][2] == 1 && visited[2] == 0 -> q.push(2); -> 현재 큐: {2}
    • visited[2] = 1
  • 큐가 비어있지 않으므로 while문 실행
    • V = 2
    • q.pop() -> 현재 큐: {}
    • graph[2][1] == 1 && visited[1] == 1 -> 다음 반복
    • graph[2][2] != 1 -> 다음 반복
    • graph[2][3] == 1 && visited[3] == 0 -> q.push(3); -> 현재 큐: {3}
    • visited[3] = 1
  • 큐가 비어있지 않으므로 while문 실행
    • V = 3
    • q.pop() -> 현재 큐: {}
    • graph[3][1] == 1 && visited[3] == 1 -> 다음 반복
    • graph[3][2] == 1 && visited[2] == 1 -> 다음 반복
    • graph[3][3] != 1 -> 다음 반복
    • graph[3][4] == 1 && visited[4] == 0 -> q.push(4); -> 현재 큐: {4}
    • visited[4] = 1
  • 큐가 비어있지 않으므로 while문 실행
    • V = 4
    • q.pop() -> 현재 큐: {}
    • graph[4][1] == 1 && visited[1] == 1 -> 다음 반복
    • graph[4][2] == 1 && visited[2] == 1 -> 다음 반복
    • graph[4][3] == 1 && visited[3] == 1 -> 다음 반복
    • graph[4][4] != 1 -> 다음 반복
    • N이 4이므로 for문 종료
  • 큐가 비어있으므로 while문 종료
  • 출력된 순서는 1 2 3 4