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

🎁 문제 링크

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

🎁 문제 설명

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

🎁 입출력 예시

🎁 그림 표현

🎁 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        //트리 구조 표현 리스트
        ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            tree.add(new ArrayList<>());
        }

        for (int i = 0; i < N - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            tree.get(a).add(b);
            tree.get(b).add(a);
        }

        int[] parentNode = new int[N + 1];	//Tree 저장을 위한 1차배열(Root는 1부터 시작 => n + 1)
        boolean[] visited = new boolean[N + 1];

        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        visited[1] = true;
        while(!queue.isEmpty()){
            int v = queue.remove();
            for(int i : tree.get(v)){
                if(!visited[i]){
                    visited[i] = true;
                    queue.add(i);
                    parentNode[i] = v;
                }
            }
        }

        //root = 1이기 때문에 2부터 시작
        for (int i = 2; i <= N; i++) {
            System.out.println(parentNode[i] + " ");
        }

    }
}