[백준] 24480 : 알고리즘 수업 - 깊이 우선 탐색 2

문제 출처: https://www.acmicpc.net/problem/24480

소요 시간: 시도 & 풀이(10m)

---

문제

---

풀이

 

앞서 풀었던 깊이 우선 탐색 1의 코드에서 정렬을 오름차순에서 내림차순으로 바꾸면 되는 간단한 문제였다.

 

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.StringTokenizer;
import java.util.ArrayList;

public class Main {

    private static int N, M, R;
    private static int[] visited;
    private static ArrayList<ArrayList<Integer>> E;
    private static int idx = 1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());    // 5 ~ 100,000
        M = Integer.parseInt(st.nextToken());    // 1 ~ 200,000
        R = Integer.parseInt(st.nextToken());    // 1 ~ N

        visited = new int[N + 1];
        E = new ArrayList<>();
        for (int i = 0; i <= N; i++) E.add(new ArrayList<>());

        int u, v;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());

            E.get(u).add(v);
            E.get(v).add(u);
        }

        for (int i = 1; i <= N; i++) {
            Collections.sort(E.get(i), Collections.reverseOrder());
        }

        dfs(R);

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            sb.append(visited[i]).append("\n");
        }

        System.out.print(sb);
    }

    private static void dfs(int R) {
        visited[R] = idx++;

        for(int v : E.get(R)) {
            if (visited[v] == 0) dfs(v);
        }
    }
}