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

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

풀이

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

public class Main {
    static ArrayList<Integer> [] graph;
    static int[] parent;
    static boolean[] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        graph = new ArrayList[n + 1];
        visit = new boolean[n + 1];
        parent = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            graph[i] = new ArrayList<>();
        }

        StringTokenizer st;
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int to = Integer.parseInt(st.nextToken());
            int from = Integer.parseInt(st.nextToken());
            graph[to].add(from);
            graph[from].add(to);
        }

        dfs(1);
        for (int i = 2; i <= n; i++)
            System.out.println(parent[i]);
    }

    static void dfs(int start) {
        for (int child : graph[start]) {
            if (visit[child]) continue;
            parent[child] = start;
            visit[child] = true;
            dfs(child);
        }
    }

}

• n의 최대값이 100,000이므로 인접 행렬로 구현할 경우 100,000*100,000 .. 런타임 에러가 발생한다.
  인접 리스트로 구현해주자.
• 이전에는 잘 풀지 못했던 트리 순회 문제도 dfs가 나름 익숙해지니 잘 풀리는 게 신기해서 기록해둔다 ㅎㅎ