[BOJ 1260번/C++] DFS와 BFS

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

DFS와 BFS

문제

문제

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

 

제한사항

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

풀이

DFS와 BFS를 활용하는 기초문제!

문제 풀이에도 자주 쓰이는 알고리즘이기 때문에 반드시 알아두어야 할 알고리즘이다.

 

[알고리즘] 너비 우선 탐색(BFS) / 깊이 우선 탐색(DFS)

[알고리즘] 너비 우선 탐색(BFS) / 깊이 우선 탐색(DFS)

 

[함께 풀기]

알고리즘 수업 - 깊이 우선 탐색 1

알고리즘 수업 - 깊이 우선 탐색 2

알고리즘 수업 - 너비 우선 탐색 1

알고리즘 수업 - 너비 우선 탐색 2

 

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

vector<vector<int>> grp;
vector<bool> d_visited;
vector<bool> b_visited;
queue<int> q;
int N, M, R;

void dfs(int r) {
    d_visited[r] = true;
    printf("%d ", r);

    int g_size = grp[r].size();
    for (int i = 0; i < g_size; i++) {
        if (!d_visited[grp[r][i]]) {
            dfs(grp[r][i]);
        }
    }
}

void bfs(int r) {
    b_visited[r] = true;
    q.push(r);

    while (!q.empty()) {
        int n = q.front();
        q.pop();
        printf("%d ", n);

        int g_size = grp[n].size();
        for (int i = 0; i < g_size; i++) {
            if (!b_visited[grp[n][i]]) {
                q.push(grp[n][i]);
                b_visited[grp[n][i]] = true;
            }
        }
    }
}

int main() {
    scanf("%d %d %d", &N, &M, &R);

    grp.resize(N + 1);
    d_visited.resize(N + 1);
    b_visited.resize(N + 1);
    int n1;
    int n2;
    for (int i = 0; i < M; i++) {
        scanf("%d %d", &n1, &n2);
        grp[n1].push_back(n2);
        grp[n2].push_back(n1);
    }
    for (int i = 1; i <= N; i++) {
        sort(grp[i].begin(), grp[i].end());
    }

    dfs(R);
    printf("\n");
    bfs(R);

    return 0;
}