[BOJ 24480번] 알고리즘 수업 - 깊이 우선 탐색 2 (Java)

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

24480번: 알고리즘 수업 - 깊이 우선 탐색 2

 

문제 해결 프로세스

 

이 문제는 이전 깊이 우선 탐색 1 문제와 완전히 동일하지만, 정점을 내림차순으로 방문합니다.

Collections.reverseOrder() 을 이용하여 리스트만 내림차순으로 정렬해주면 해결되지만,

DFS 알고리즘에 익숙해지기 위해 다시 한 번 풀어보는 것을 추천해드립니다!

 

정답 코드

package DFS완전정복;

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

public class Main_BJ_24480_알고리즘수업_깊이우선탐색2 {
    static int N, M, R;

    static ArrayList<Integer>[] adjList;
    static boolean[] visited;
    static int[] answer;
    static int cnt = 1;

    static StringBuilder sb = new StringBuilder();

    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());
        M = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        visited = new boolean[N+1];
        answer = new int[N+1];
        adjList = new ArrayList[N+1];
        for (int i = 1; i <= N; i++) {
            adjList[i] = new ArrayList<Integer>();
        }

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

        for (int i = 1; i <= N; i++) {
            adjList[i].sort(Collections.reverseOrder());
        }

        dfs(R);

        for (int i = 1; i <= N; i++) {
            sb.append(answer[i]).append('\n');
        }

        System.out.println(sb);
    }
    private static void dfs(int n) {
        visited[n] = true;
        answer[n] = cnt++;

        for (int num : adjList[n]) {
            if (!visited[num]) {
                dfs(num);
            }
        }
    }
}