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

• 백준 문제 URL

---

문제 요약

루트가 1인 트리가 주어질 때, 각 노드의 부모 노드 번호를 출력하는 문제다.
입력은 N(노드 개수)과 N-1개의 간선으로 주어지고, 출력은 2번 노드부터 N번 노드까지의 부모를 한 줄에 하나씩 출력한다.

---

핵심 아이디어

트리는 사이클이 없지만, 입력은 “부모/자식 방향 없이” 양방향 간선으로 들어온다.
그래서 루트(1)에서부터 DFS(또는 BFS)로 한 번 탐색하면서, “다음으로 처음 방문하게 되는 노드”의 부모를 현재 노드로 기록하면 된다.

즉, 탐색 중에 parent[child] = current를 찍어주면 부모 배열이 완성된다.

---

입력 처리 & 인접 리스트 구성

간선 목록으로 들어온 입력을 인접 리스트로 만든 뒤, 양방향 그래프 형태로 저장한다.

• adjList.get(a).add(b)
• adjList.get(b).add(a)

그리고 방문 순서를 일정하게 맞추고 싶으면(필수는 아님) 각 리스트를 오름차순 정렬한다.

for (int i = 0; i < node + 1; i++) {
    adjList.add(new ArrayList<>());
}

for (int i = 0; i < node - 1; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    int nodeA = Integer.parseInt(st.nextToken());
    int nodeB = Integer.parseInt(st.nextToken());
    adjList.get(nodeA).add(nodeB);
    adjList.get(nodeB).add(nodeA);
}

for (List<Integer> list : adjList) {
    list.sort(Comparator.naturalOrder());
}

---

DFS로 부모 기록하기

상태 정의

• visited[x] : x를 이미 방문했는지
• parent[x] : x의 부모가 누구인지 (루트는 부모가 없으니 0 유지)

핵심 로직

현재 노드 start에서 인접 노드 target을 보면서, 방문하지 않았다면:

• parent[target] = start 로 부모 기록
• dfs(target) 로 내려가기

static void dfs(int start) {
    visited[start] = true;

    for (int target : adjList.get(start)) {
        if (!visited[target]) {
            parent[target] = start;
            dfs(target);
        }
    }
}

---

출력

문제 요구가 “2번 노드부터 N번 노드까지”의 부모 출력이라서, parent[2] ~ parent[N]만 출력하면 된다.

for (int i = 2; i <= node; i++) {
    System.out.println(parent[i]);
}

---

전체 코드(제출용)

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

public class Main {
    static int node;
    static List<List<Integer>> adjList = new ArrayList<>();
    static int[] parent;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        node = Integer.parseInt(br.readLine());

        visited = new boolean[node + 1];
        parent = new int[node + 1];

        for (int i = 0; i < node + 1; i++) adjList.add(new ArrayList<>());

        for (int i = 0; i < node - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int nodeA = Integer.parseInt(st.nextToken());
            int nodeB = Integer.parseInt(st.nextToken());
            adjList.get(nodeA).add(nodeB);
            adjList.get(nodeB).add(nodeA);
        }

        for (List<Integer> list : adjList) list.sort(Comparator.naturalOrder());

        dfs(1);

        for (int i = 2; i <= node; i++) {
            System.out.println(parent[i]);
        }
    }

    static void dfs(int start) {
        visited[start] = true;
        for (int target : adjList.get(start)) {
            if (!visited[target]) {
                parent[target] = start;
                dfs(target);
            }
        }
    }
}