백준 1260 DFS와 BFS [C++]

작성일 | In |

Problem : DFS와 BFS

유형 : DFS, BFS

문제 해석

  • 그래프를 DFS와 BFS로 탐색한 결과를 내놓아라
    • 양방향 그래프이다.
    • 방문하는 정점은 오름차순 순으로 방문한다

해결 전략

  • 정렬한다.
  • DFS, BFS를 진행한다.

설계, 구현

  • 인접 리스트를 통해 그래프간의 연결관계를 정해둔다.
  • 재귀를 이용한 DFS
  • 큐를 이용한 BFS를 진행한다.

주의할 점

  • 방문하는 정점은 오름차순 순인것을 잊으면 안된다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1002;

vector<int> node[MAX];
bool visited[MAX];

int n, m, startNode;

void bfs(int startNode) {
    queue<int> q;
    visited[startNode] = true;
    q.push(startNode);
    
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        cout << cur << " ";
        
        for (const int& nextNode : node[cur]) {
            if (visited[nextNode]) continue;
            visited[nextNode] = true;
            q.push(nextNode);
        }
    }
    cout << "\n";
}

void dfs(int curNode) {
    cout << curNode << " ";
    for (const int& nextNode : node[curNode]) {
        if (visited[nextNode]) continue;
        visited[nextNode] = true;
        dfs(nextNode);
    }
}

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

void solve() {
    cin >> n >> m >> startNode;
    while (m--) {
        int s, e;
        cin >> s >> e;
        node[s].push_back(e);
        node[e].push_back(s);
    }

    graphSort();
    
    visited[startNode] = true;
    dfs(startNode);
    cout << "\n";

    memset(visited, false, sizeof(visited));
    bfs(startNode);
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    solve();

    return 0;
}

피드백

  • 없음