[백준] 1260번 : DFS와 BFS

문제

 

---

풀이

 

그래프 탐색 방법에 속하는 DFS와 BFS를 구현하는 문제이다.

DFS는 깊이 우선 탐색으로 보통 스택 또는 재귀로 구현한다.

BFS는 너비 우선 탐색으로 보통 큐로 구현한다.

 

BFS와 DFS의 그래프 순회 순서를 나타낸 그림이다.

대충 BFS는 왼쪽->오른쪽, DFS는 위->아래로 생각하면 된다.

---

소스코드

 

#include <iostream>
#include <cstring>
#include <stack>
#include <queue>

using namespace std;

int matrix[1001][1001]; //정점 i와 j 사이에 간선이 존재하면 matrix[i][j]=1
bool visited[1001] = {false}; //정점의 방문 여부

void dfs(int start, int max) { //스택으로 구현, 재귀로 구현해도 됨
    stack<int> s;

    s.push(start);
    while (!s.empty()) {
        int cur = s.top();
        s.pop();
        if (!visited[cur]) { //스택에 들어갈 땐 !visited 였으나 나온 순간에는 아닐 수도 있음
            visited[cur] = true;
            cout << cur << ' ';
            for (int i = max; i >= 1; i--) { //연결된 정점 중 아직 방문하지 않은 정점을 스택에 넣음
                if (matrix[cur][i] == 1 && !visited[i])
                    s.push(i);
            }
        }
    }
}

void bfs(int start, int max) { //큐로 구현
    queue<int> q;

    q.push(start);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        if (!visited[cur]) { //큐에 들어갈 땐 !visited 였으나 나온 순간에는 아닐 수도 있음
            visited[cur] = true;
            cout << cur << ' ';
            for (int i = 1; i <= max; i++) { //연결된 정점 중 아직 방문하지 않은 정점을 큐에 넣음
                if (matrix[cur][i] == 1 && !visited[i])
                    q.push(i);
            }
        }
    }
}

int main() {
    int N, M, V, first, second;

    cin >> N >> M >> V;
    for (int i = 0; i < M; i++) {
        cin >> first >> second;
        matrix[first][second] = 1;
        matrix[second][first] = 1;
    }
    dfs(V, N);
    memset(visited, false, sizeof(visited));
    cout << '\n';
    bfs(V, N);
}

스택으로 구현한 DFS와 큐로 구현한 BFS이다.

 

int matrix[1001][1001]; //정점 i와 j 사이에 간선이 존재하면 matrix[i][j]=1
bool visited[1001] = {false}; //정점의 방문 여부

정점 사이의 연결관계를 저장할 matrix와 정점의 방문 여부를 저장할 visited이다.

 

    for (int i = 0; i < M; i++) {
        cin >> first >> second;
        matrix[first][second] = 1;
        matrix[second][first] = 1;
    }

양방향 간선이기 때문에 1 2의 입력이 들어오면 matrix[1][2]와 matrix[2][1] 모두 표시해야 한다.

 

void dfs(int start, int max) { //스택으로 구현, 재귀로 구현해도 됨
    stack<int> s;

    s.push(start);
    while (!s.empty()) {
        int cur = s.top();
        s.pop();
        if (!visited[cur]) { //스택에 들어갈 땐 !visited 였으나 나온 순간에는 아닐 수도 있음
            visited[cur] = true;
            cout << cur << ' ';
            for (int i = max; i >= 1; i--) { //연결된 정점 중 아직 방문하지 않은 정점을 스택에 넣음
                if (matrix[cur][i] == 1 && !visited[i])
                    s.push(i);
            }
        }
    }
}

스택으로 구현한 dfs다. 그림으로 예제 입력 1에 대한 코드 진행 과정을 설명하겠다.

 

 

void bfs(int start, int max) { //큐로 구현
    queue<int> q;

    q.push(start);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        if (!visited[cur]) { //큐에 들어갈 땐 !visited 였으나 나온 순간에는 아닐 수도 있음
            visited[cur] = true;
            cout << cur << ' ';
            for (int i = 1; i <= max; i++) { //연결된 정점 중 아직 방문하지 않은 정점을 큐에 넣음
                if (matrix[cur][i] == 1 && !visited[i])
                    q.push(i);
            }
        }
    }
}

큐로 구현한 bfs다. 그림으로 예제 입력 1에 대한 코드 진행 과정을 설명하겠다.