(Java) 백준 11725 - 트리의 부모 찾기

문제를 풀다 보니 트리에 약점이 있는 것 같아 트리 문제를 풀어보았다.

문제 이해가 좀 어려웠다. 문제에 어떤 트리인지 특정하지 않아서 생각하기 더 어려웠나?

인접 행렬이나 인접 리스트를 만들면 탐색은 금방 할 것 같았는데 인접 리스트를 만드는 게 어려웠다.

트리 문제를 더 풀어봐야겠다.

---

최종 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());

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

        // 인접 리스트 만들기
        List<ArrayList<Integer>> list = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            list.add(new ArrayList());
        }

        // 입력값으로 인접 리스트 삽입
        for (int i = 1; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());

            list.get(left).add(right);
            list.get(right).add(left);
        }

        // BFS
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        visited[1] = true;
        while (!queue.isEmpty()) {
            int temp = queue.poll();
            for (int i : list.get(temp)) {
                if (!visited[i]) {
                    visited[i] = true;
                    queue.add(i);
                    parent[i] = temp;
                }
            }
        }

        // 출력
        for (int i = 0; i < parent.length; i++) {
            if ((parent[i] != 0)) {
                if (i == parent.length - 1) {
                    sb.append(parent[i]);
                } else {
                    sb.append(parent[i]).append("\n");
                }
            }
        }

        System.out.println(sb.toString());

    }
}