[자바] 백준 24480 - 알고리즘 수업 - 깊이 우선 탐색 2 (boj java)

문제 : boj24480

 

    내림차순으로 다음 정점을 선택해야 한다. 이걸 위해 인접 행렬로 간선을 저장할 경우 O(N^2)이 필요하므로 시간초과가 나게 될 것이다. 그러니 인접 리스트로 간선을 표현하자. 이 때 내림차순으로 다음 정점을 선택해야 하므로, 미리 내림차순으로 각 정점의 간선들을 정렬시켜두면 된다. 혹은 Priority Queue 등을 사용해 다음 정점을 저장해둬도 될 것이다.

  위의 내용 이외에는 기본 DFS로 구현하면 된다.

 

코드 : github

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

public class Main {
    int[] answer;
    ArrayList<Integer>[] edges;
    int idx = 0;
    boolean[] v;

    private void dfs(int cur) {
        answer[cur] = ++idx;
        for (int next : edges[cur]) {
            if (v[next]) continue;
            v[next] = true;
            dfs(next);
        }
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());
        edges = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) edges[i] = new ArrayList<>();
        answer = new int[n+1];
        v = new boolean[n+1];
        while (m-->0) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            edges[u].add(v);
            edges[v].add(u);
        }
        for (int i = 1; i <= n; i++) Collections.sort(edges[i], Collections.reverseOrder());
        v[r] = true;
        dfs(r);
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) sb.append(answer[i]).append('\n');
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}