[백준 11725] 트리의 부모 찾기

문제

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

---

접근

• 인접 리스트로 트리 생성
• DFS 로 루트 노드 1부터 탐색
  • 탐색 시 해당 노드의 부모를 parents 배열에 기록한다.
  • 노드 탐색 시 다시 부모 노드를 탐색하지 않기 위해 주의!

---

코드

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

public class TreeParent_11725 {
    static List<Integer>[] tree;
    static int[] parents;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        tree = new List[N + 1];
        parents = new int[N + 1];

        for (int i = 1; i < N + 1; i++) {
            tree[i] = new ArrayList<>();
        }
        for (int i = 1; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());
            tree[node1].add(node2);
            tree[node2].add(node1);
        }

        dfs(1, 0);

        StringBuffer sb = new StringBuffer();
        for (int i = 2; i < N + 1; i++) {
            sb.append(parents[i] + "\n");
        }
        System.out.print(sb.toString());

    }
    // 각 노드를 탐색하면서 자식 노드의 부모를 기록
    static void dfs(int node, int parent) {
        parents[node] = parent;
        for (int child : tree[node]) {
            if (child != parent) {
                dfs(child, node);
            }
        }
    }
}