백준 11725: 트리의 부모 찾기 [Java] -포포

문제

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

입력

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

출력

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

---

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

public class Main{
    static int n;
    static int[] parent;
    static boolean[] visit;
    static ArrayList<Integer>[] list;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        StringTokenizer st;
        parent = new int[n + 1];
        visit = new boolean[n + 1];

        list = new ArrayList[n + 1];

        for (int i = 0; i <= n; i++) {
            list[i] = new ArrayList<>();
        }

        int a, b;
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());

            list[a].add(b);
            list[b].add(a);
        }
        visit[1] = true;
        dfs(1);

        StringBuilder sb = new StringBuilder();
        for (int i = 2; i <= n; i++) {
            sb.append(parent[i]).append('\n');
        }

        System.out.println(sb);
    }

    private static void dfs(int start) {
        for(int a : list[start]){
            if(!visit[a]){
                parent[a] = start;
                visit[a] = true;
                dfs(a);
            }
        }
    }
}

먼저, 노드의 개수(N)가 최대 100,000이므로 이중 배열이 아닌 ArrayList[]로 해결했다.
이중 배열로 해결하려고 하면 메모리 초과가 발생한다.

1번 노드부터 시작하여 연결된 다음 노드로 이동한다. 이동하기 전에, 방문처리를 해준 뒤
parent[다음 노드의 인덱스] = 현재 노드 번호 설정이 필요하다.
입력한 뒤 탐색이 종료되면 parent 배열을 출력한다.