DFS와 BFS

문제: DFS와 BFS (백준 1260번)

구조 분석

정점의 개수와 간선의 개수를 입력받고 간선 정보를 입력한 뒤 해당 graph에 대해 DFS와 BFS를 실시하는 문제이다.

풀이 방법

DFS는 stack을 사용한다. 이때 주의할 점은 방문한 노드를 재방문 하지 않도록 설정해야 한다. 또한 해당 문제의 경우 노드(1)와 노드(2), 노드(3), 노드(4)가 연결되어 있다고 할 때, 노드 (2)부터 방문하므로 stack에 넣을 때, 숫자가 큰 순서대로 넣어야 한다.
BFS는 queue를 사용한다. Queue의 경우 FIFO이므로 먼저 방문할 노드 먼저 넣어주면 된다.

코드

#include <stdio.h>
#include <iostream>
#include <queue>
#include <stack>
using namespace std;

int n, m, v;
int edge[1001][1001] = {0,};
int visited[1001] = {0,};

void init() {
    for (int i=0; i<1001; i++) {
        visited[i] = 0;
    }
}

void dfs(int x) {
    stack<int> S;
    S.push(x);
    while (!S.empty()) {
        x = S.top();
        if (visited[x] == 1) {
            S.pop();
            continue;
        }
        visited[x] = 1;
        cout << x << " ";
        S.pop();
        for (int i=n; i>0; i--) {
            if (edge[x][i] == 1 && visited[i] == 0) {
                S.push(i);
            }
        }
    }
}

void bfs(int x) {
    queue<int> Q;
    Q.push(x);
    visited[x] = 1;
    cout << x << " ";
    while (!Q.empty()) {
        x = Q.front();
        Q.pop();
        for (int i=1; i<=n; i++) {
            if (edge[x][i] == 1 && visited[i] == 0) {
                Q.push(i);
                visited[i] = 1;
                cout << i << " ";
            }
        }
    }
}

int main() {
    cin >> n >> m >> v;
    int v1, v2;
    for (int i=0; i<m; i++) {
        cin >> v1 >> v2;
        edge[v1][v2] = 1;
        edge[v2][v1] = 1;
    }
    dfs(v);
    cout << "\n";
    init();
    bfs(v);
    cout << "\n";
    return 0;
}

정리

해당 문제는 graph를 DFS와 BFS로 각각 풀어보는 기본적인 문제였다.