[BOJ] 11725. 트리의 부모 찾기

문제

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

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

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

해결 방법

• 트리 상에서 연결된 두 정점이 입력으로 주어지고, 각 노드의 부모 노드 번호를 출력하는 문제
• bfs 를 활용한다면 부모 노드를 바로 알 수 있다.
• 배열로 풀면 메모리 초과가 뜬다
  • 연결 리스트를 사용해야 한다
• result 배열 i번째에 parent를 넣으면 노드 순서대로 부모가 출력된다.

코드

// 트리의 부모 찾기, 11725
public class Week05_11725 {
    static List<List<Integer>> tree;
    static boolean[] visited;
    static int n;
    static int[] result;

    public static void main(String[] args) throws IOException {
        input();
        bfs();
        output();
    }

    private static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 2; i < result.length; i++) {
            bw.write(result[i] + "\n");
        }
        bw.flush();
        bw.close();
    }

    private static void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        visited[1] = true;
        queue.add(1);
        while (!queue.isEmpty()) {
            int parent = queue.poll();
            for (int i : tree.get(parent)) {
                if (!visited[i]) {
                    visited[i] = true;
                    queue.add(i);
                    result[i] = parent;
                }
            }
        }
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        tree = new ArrayList<>();
        visited = new boolean[n + 1];
        result = new int[n + 1];

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

        for (int i = 1; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            tree.get(u).add(v);
            tree.get(v).add(u);
        }
    }
}