트리의 부모 찾기

문제

11725번: 트리의 부모 찾기

문제 설명

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

제한 사항

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

출력

입출력 예

입력	출력

| 7
1 6
6 3
3 5
4 1
2 4
4 7 | 4
6
1
3
1
4 |
| 12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12 | 1
1
2
3
3
4
4
5
5
6
6 |

아이디어

BFS

제출 코드

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

public class two11725 {
    public void solution() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int nodeCnt = Integer.parseInt(reader.readLine());
        List<List<Integer>> tree = new ArrayList<>();

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

        for (int i = 0; i < nodeCnt - 1; i++) {
            StringTokenizer treeToken = new StringTokenizer(reader.readLine());
            int nodeOne = Integer.parseInt(treeToken.nextToken()) - 1;
            int nodeTwo = Integer.parseInt(treeToken.nextToken()) - 1;

            tree.get(nodeOne).add(nodeTwo);
            tree.get(nodeTwo).add(nodeOne);
        }

        boolean[] visited = new boolean[nodeCnt];
        int[] parent = new int[nodeCnt];

        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        visited[0] = true;
        while (!queue.isEmpty()) {
            int currentNode = queue.remove();
            for (int node : tree.get(currentNode)) {
                if (!visited[node]) {
                    queue.add(node);
                    visited[node] = true;
                    parent[node] = currentNode;
                }
            }
        }
        for (int i = 1; i < nodeCnt; i++) {
            System.out.println(parent[i] + 1);
        }
    }

    public static void main(String[] args) throws IOException {
        new two11725().solution();
    }
}