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

 

 

풀이

• 각 정점에서 연결된 정점들을 번호순으로 처리하기 위해 정렬한다.
• DFS 함수에서는 현재 정점을 방문하고, 방문했다는 표시를 한 뒤, 현재 정점에 연결된 정점들을 재귀적으로 방문한다.
• BFS 탐색은 큐를 이용하여 구현한다.
• DFS 함수와 BFS 함수에서 visited 배열을 공유하지 않도록 주의하면서 구현하면 된다.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

vector<int> graph[1001];
bool visited[1001];

void dfs(int node) {
    visited[node] = true;
    cout << node << " ";
    for(int next : graph[node]) {
        if(!visited[next]) {
            dfs(next);
        }
    }
}

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while(!q.empty()) {
        int curr = q.front();
        q.pop();
        cout << curr << " ";
        for(int next : graph[curr]) {
            if(!visited[next]) {
                visited[next] = true;
                q.push(next);
            }
        }
    }
}

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

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

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

    dfs(v);
    cout << "\n";
    fill_n(visited, 1001, false);
    bfs(v);
    cout << "\n";

    return 0;
}

 

 

 

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

1260번: DFS와 BFS