DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 1

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

예제 출력 1

1 2 4 3
1 2 3 4

예제 입력 2

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

예제 출력 2

3 1 2 5 4
3 1 4 2 5

예제 입력 3

1000 1 1000
999 1000

예제 출력 3

1000 999
1000 999

방문 순서를 어떻게 보장할까

예제 1에서 1의 이웃은 2, 3, 4다. DFS는 가장 작은 2로 들어간 뒤, 2에서 아직 방문하지 않은 4로 더 깊이 간다. 4에서 3을 방문하므로 1 2 4 3이 된다. BFS는 1을 꺼낼 때 2, 3, 4를 순서대로 큐에 넣어 1 2 3 4를 만든다. 그래프가 같아도 자료구조와 방문 시점이 달라 순서가 달라진다.

입력의 간선 순서가 작은 번호 순서라는 보장은 없다. 그래서 양방향 인접 리스트를 만든 뒤 각 정점의 이웃 목록을 오름차순으로 정렬한다. DFS는 정점에 들어갈 때 방문 표시를 하고, BFS는 큐에 넣을 때 표시한다. 큐에서 꺼낼 때까지 표시를 미루면 같은 정점이 여러 번 들어갈 수 있다. 두 탐색은 서로 독립적이므로 방문 배열도 분리한다.

시작점에서 닿지 않는 정점은 출력하지 않는다. 중복 간선이나 자기 자신으로 향하는 간선이 있어도 방문 표시가 중복 출력을 막는다. 인접 리스트 저장은 O(N+M), 탐색은 각각 O(N+M)이고, 이웃 정렬은 모든 정점의 차수에 대해 O(∑deg(v) log deg(v))이다. DFS 재귀 깊이는 최악에 N까지 늘 수 있으므로 더 큰 그래프에서는 명시적 스택도 고려한다.

처리 순간	DFS에서 새로 방문한 정점	BFS 큐
시작점 1	1	[1]
1의 이웃 처리	2로 재귀 진입	[2, 3, 4]
다음 정점	4로 더 깊이 감	2를 꺼내고 [3, 4]
탐색 완료	3을 방문	3, 4를 순서대로 꺼냄

BFS의 큐에 이미 들어간 4는 2에서 다시 만났더라도 추가하지 않는다. 이 차이가 DFS의 4→3 방문과 BFS의 3→4 방문을 갈라 놓는다.

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static List<List<Integer>> graph;
    static boolean[] visited;
    static StringBuilder order;

    static void dfs(int vertex) {
        visited[vertex] = true;
        order.append(vertex).append(' ');
        for (int next : graph.get(vertex)) {
            if (!visited[next]) dfs(next);
        }
    }

    static void bfs(int start, int size) {
        boolean[] seen = new boolean[size + 1];
        Queue<Integer> queue = new ArrayDeque<>();
        seen[start] = true;
        queue.add(start);
        while (!queue.isEmpty()) {
            int vertex = queue.remove();
            order.append(vertex).append(' ');
            for (int next : graph.get(vertex)) {
                if (!seen[next]) {
                    seen[next] = true;
                    queue.add(next);
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());
        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(in.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph.get(a).add(b);
            graph.get(b).add(a);
        }
        for (List<Integer> neighbors : graph) Collections.sort(neighbors);

        visited = new boolean[n + 1];
        order = new StringBuilder();
        dfs(start);
        String dfsOrder = order.toString().trim();
        order.setLength(0);
        bfs(start, n);
        System.out.println(dfsOrder);
        System.out.println(order.toString().trim());
    }
}

백준 원문 문제