🔍 문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

🔍 풀이

탐색 알고리즘

완전 탐색 알고리즘에는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)이 있고, 이것을 이용하는 문제이다.
구현에 있어서 스택과 큐, 재귀함수와 긴밀한 연관이 있으므로 앞선 개념들을 이해해야 한다.

DFS - 깊이 우선 탐색

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
재귀 또는 스택을 이용하여 구현할 수 있으며, 구체적인 동작 과정은 다음과 같다.

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

BFS - 너비 우선 탐색

가까운 노드를 우선적으로 탐색하는 알고리즘이다.
선입선출 방식인 큐 알고리즘을 이용하며, 구체적인 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
   (방문 처리를 함으로써 한번 처리된 노드가 다시 스택에 삽입되지 않게 함)
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 수행할 수 없을 때 까지 반복한다.

🔍 구현

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

int N, M, V; // 정점의 개수 N, 간선의 개수 M, 시작 정점 V
int map[1001][1001]; // 인접 행렬 그래프
bool visited[1001]; // 정점 방문 여부
queue<int> q;

void DFS(int v){
    visited[v] = true; // 방문 처리
    cout << v << " "; // 방문 노드 출력

    for (int i = 1; i <= N ; i++){
        if (map[v][i] == 1 && visited[i] == 0)
            DFS(i);
    }
}

void BFS(int v){
    q.push(v);
    visited[v] = true;
    cout << v << " ";

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

        for (int i = 1; i <= N; i++){
            if (map[v][i] == 1 && visited[i] == 0) { // 현재 정점과 연결되어 있고 방문되지 않았다면
                q.push(i);
                visited[i] = true;
                cout << i << " ";
            }
        }
    }
}

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

    for (int i = 0; i < M; i++){ // 인접한 노드들 map 배열 값 1로 바꾸기
        int a, b;
        cin >> a >> b;
        map[a][b] = 1;
        map[b][a] = 1;
    }

    DFS(V);
    cout <<"\n";

    fill_n(visited, 1001, 0); // 초기화
    visited[V] = 1;
    BFS(V);

    return 0;
}