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

문제 : boj24479

 

  단순한 dfs 문제로 보이겠으나, 문제는 '오름차순' 부분이다. 이걸 위해 인접 행렬로 간선을 저장할 경우 O(N^2)이 필요하므로 시간초과가 나게 될 것이다. 그러니 인접 리스트로 간선을 표현하는게 좋고, 미리 오름차순으로 각 정점의 간선들을 정렬시켜두면 이 문제에서는 인접 행렬의 경우보다 시간도 덜 들고 메모리도 덜 들어 더 효율적으로 짤 수 있다.

 

  위의 전처리 이외에는 기본 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]);
        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();
    }
}