백준 1260번 - DFS와 BFS

백준 1260번 - DFS와 BFS

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

문제

• 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오.

• 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다.

입력

• 첫째 줄에 정점의 개수 N(1≤N≤1,000), 간선의 개수 M(1≤M≤10,000), 탐색을 시작할 정점의 번호 V가 주어진다.

• 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다.

• 한 간선이 여러 번 주어질 수도 있는데, 간선이 하나만 있는 것으로 생각하면 된다. 입력으로 주어지는 간선은 양방향이다.

출력

• 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다.

• V부터 방문된 점을 순서대로 출력하면 된다.

접근

• 벡터로 인접리스트를 생성한다.

• BFS와 DFS로 구현한다.

• 방문할 수 있는 정점이 여러개인 경우, 정점 번호가 낮은 것 부터 방문해야 한다.

  • 큐를 활용하는 BFS는 방문할 수 있는 정점을 오름차순으로 정렬하여 번호가 가장 낮은 정점이 front에 위치하도록 한다.

  • 스택을 활용하는 DFS는 방문할 수 있는 정점을 내림차순으로 정렬하여 번호가 가장 낮은 정점이 top에 위치하도록 한다.

C++ Code

#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;
​
vector<vector<int>> adj;
vector<bool> visited;
int n, m, v;
int a, b;
​
void bfs(int v) {
    queue<int> q;
    q.push(v);
​
    while (!q.empty()) {
        int front = q.front();
        q.pop();
        if (visited[front]) continue;
​
        visited[front] = true;
        printf("%d ", front);
​
​
        sort(adj[front].begin(), adj[front].end());
        for (int i = 0; i < adj[front].size(); i++) {
            q.push(adj[front][i]);
        }
    }
    printf("\n");
}
​
void dfs(int v) {
    stack<int> s;
    s.push(v);
​
    while (!s.empty()) {
        int top = s.top();
        s.pop();
        if (visited[top]) continue;
​
        visited[top] = true;
        printf("%d ", top);
​
        sort(adj[top].begin(), adj[top].end(), greater<int>());
        for (int i = 0; i < adj[top].size(); i++) {
            if (!visited[adj[top][i]]) s.push(adj[top][i]);
        }
    }
    printf("\n");
}
​
int main(void) {
    scanf("%d %d %d", &n, &m, &v);
    adj.resize(n + 1);
    visited.resize(n + 1);
​
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
​
    dfs(v);
​
    fill_n(visited.begin(), n + 1, false);
    bfs(v);
​
    return 0;
}