Computer Science & Engineering

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

이 문제는 비 방향성 그래프의 간선이 주어졌을 때 V번 정점부터 시작하여 DFS로 탐색한 결과와 BFS로 탐색한 결과를 각각 출력하는 기본적인 그래프 탐색 문제이다. 입력은 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점 번호 V와 M개의 간선들로 이루어진다. 코드는 아래와 같다.

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

const int MN = 1001;

vector<int> g[MN]; //인접 리스트
bool vst[MN]; //방문 여부
void dfs(int N) { //DFS
    vst[N] = true; //방문 체크
    cout << N << ' '; //방문한 노드 번호 출력
    for(int e : g[N]) { //방문한 노드로부터 인접 리스트를 확인
        if(!vst[e]) dfs(e); //방문하지 않은 노드 방문
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M, V; cin >> N >> M >> V;
    for(int i = 0; i < M; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v); //인접리스트 추가
        g[v].push_back(u);
    }
    for(int i = 1; i <= N; i++) { //정점 번호 오름차순으로 정렬
        sort(g[i].begin(), g[i].end());
    }
    dfs(V); //V번 정점부터 DFS
    cout << "\n" << V; //DFS출력 마지막을 나타내는 개행 후 BFS 시작정점 V출력
    queue<int> q; //BFS에 사용할 queue
    memset(vst, 0, sizeof(vst)); //방문 배열 초기화
    q.push(V); //시작 정점 queue에 추가
    vst[V] = true; //시작 정점 방문 체크
    while(!q.empty()) { //모든 정점을 방문할 때까지
        int now = q.front(); q.pop(); //queue의 첫 번째 pop
        for(int e : g[now]) { //인접리스트 확인
            if(!vst[e]) { //방문하지 않은 노드 발견할 경우
                cout << ' ' << e; //정점 출력
                vst[e] = 1; //방문 체크
                q.push(e); //queue에 추가
            }
        }
    }
}

방문하는 정점은 번호가 작은 것부터 우선적으로 방문해야하므로 우선 각 정점의 인접리스트를 오름차순으로 정렬한다.

    DFS를 우선적으로 출력하기 때문에 방문하지 않은 노드를 발견할 경우 곧바로 DFS로 탐색하여 정점을 출력하고 방문체크를 한다. 그 다음 그 노드로부터 인접리스트를 확인하여 더 탐색할 수 있는 정점이 있는지 확인한다. 있을 경우 재귀적으로 탐색한다.

    BFS는 queue를 이용한다. 방문한 노드를 체크하고 큐에 넣는다. 큐는 FIFO(First In First Out)이기 때문에 방문한 노드를 순서대로 확인할 수 있다. 시작정점 V를 큐에 넣고 방문 체크를 한다. 반복문은 큐가 빌때까지 반복한다. 큐의 첫 번째 원소를 pop한 후 그 원소의 인접 리스트를 확인한다. 방문하지 않은 노드를 발견할 경우 그 정점을 출력하고 방문체크를하고 큐에 push한다.

    백준에서는 개행이나 공백이 한 두개 더 출력되더라도 오답처리를 하지 않기 때문에 마지막일 경우 뒤에 공백이나 개행을 넣지 않기 위한 예외를 처리하지 않아도 된다.