깊이 우선 탐색

[주인장]

문제명: 그래프 탐색 순서 출력

N개의 정점(1~N)과 M개의 무방향 간선이 주어진다.
정점 S에서 DFS를 시작하여 방문하는 정점의 순서를 출력하라.
방문할 때는 항상 작은 번호의 정점부터 먼저 방문한다.

예시 1:

입력 

4 4 1
1 2
1 3
2 4
3 4

출력

1 2 4 3

예시 2:

입력

5 3 2
1 2
2 3
4 5

출력

2 1 3

import java.io.*;
import java.util.*;

public class Main {
    static int N, M, S;
    static List<Integer>[] graph;
    static boolean[] visited;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());

        graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) graph[i] = new ArrayList<>();

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a].add(b);
            graph[b].add(a);
        }

        for (int i = 1; i <= N; i++) {
            Collections.sort(graph[i]); // 작은 번호부터 방문
        }

        visited = new boolean[N + 1];
        dfs(S);

        System.out.println(sb.toString().trim());
    }

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