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

알고리즘 [접근 방법]

입력이 예제와 다르게 루트부터가 아닌 무작위로 나올 수도 있다.
1. 입력을 받자마자 부모와 자식 관계를 판별하는 것은 쉽지 않으니 연결된 노드를 각각 노드에 리스트를 만들어 저장한다.
2. 부모를 담을 배열을 만든다.
3. BFS를 사용하여 순회를 하며 각각의 부모 노드를 부모 배열에 담는다.

구현

class Node {

    int data;
    List<Integer> relates = new ArrayList<>();

    public Node(int data) {
        this.data = data;
    }
}
public class Main {
    static ArrayList<Node> tree = new ArrayList<>();
    static int[] parents;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter wr = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        parents = new int[n + 1];

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

        for (int i = 1; i < n; i++) {
            List<Integer> inputs = Arrays.stream(br.readLine().split(" ")).map(Integer::parseInt)
                .collect(Collectors.toList());
            tree.get(inputs.get(0)).relates.add(inputs.get(1));
            tree.get(inputs.get(1)).relates.add(inputs.get(0));
        }

        BFS();

        for (int i = 2; i < n + 1; i++) {
            wr.write(parents[i] + "\n");
        }

        wr.flush();
        wr.close();
        br.close();

    }

    private static void BFS() {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);

        while (!queue.isEmpty()) {
            Node parent = tree.get(queue.poll());
            for (Integer relate : parent.relates) {
                if (parents[relate] == 0) {
                    parents[relate] = parent.data;
                    queue.offer(relate);
                }
            }
        }
    }

}