[백준/C,C++] 1260번: DFS와 BFS

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

풀이

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 구현하는 문제입니다.

 

DFS와 BFS의 개념과 구현 방법은 생략하고,

 

현재 정점에서 여러 정점을 방문할 수 있을 때, 정점 번호가 작은 것을 먼저 방문해야 하므로,

 

그래프를 오름차순으로 정렬만 해주면 됩니다.

 

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>

using namespace std;

#define MAX 1001

int n, m, v;
vector<int> graph[MAX];
bool visited[MAX];
queue<int> q;

void DFS(int node)
{
    visited[node] = true;
    cout << node << ' ';
    size_t sz = graph[node].size();
    for (size_t i = 0; i < sz; i++) {
        int next = graph[node][i];
        if (visited[next]) continue;
        else DFS(next);
    }
}

void visit(int node)
{
    visited[node] = true;
    q.push(node);
    cout << node << ' ';
}

void BFS()
{
    visit(v);

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        size_t sz = graph[node].size();
        for (size_t i = 0; i < sz; i++) {
            int next = graph[node][i];
            if (visited[next]) continue;
            else visit(next);
        }
    }
}

int main(void)
{
    cin >> n >> m >> v;

    for (int i = 0; i < m; i++) {
        int v1, v2; cin >> v1 >> v2;
        graph[v1].push_back(v2);
        graph[v2].push_back(v1);
    }

    for (int i = 0; i < n + 1; i++) {
        sort(graph[i].begin(), graph[i].end());
    }

    DFS(v);

    cout << '\n';
    memset(visited, false, sizeof(visited));

    BFS();

    return 0;
}

반례

Input

6 6 6
1 2
2 3
3 4
4 5
5 6
1 4

Output

6 5 4 1 2 3

6 5 4 1 3 2

 

Input

8 10 5
1 2
3 4
2 5
5 6
5 8
2 7
1 4
8 3
2 8
4 6

Output

5 2 1 4 3 8 6 7

5 2 6 8 1 7 4 3