[JAVA] 11725 트리의 부모 찾기

문제

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

입력

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

출력

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

풀이과정

• 트리에서 각각 노드의 부모 노드를 출력하기 위해선 너비우선탐색을 사용
• 너비우선 탐색을 위해 Queue 사용

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class backJoon11725 {
	
    static boolean[] visited; //방문 여부     
    static ArrayList<Integer>[] List; // 트리
    static StringBuilder sb= new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        visited = new boolean[N+1];
        List = new ArrayList[N+1];
        for(int i=1;i<N+1;i++){
            List[i] = new ArrayList<Integer>();
        }
        for(int i=1;i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            //양방향 저장
            List[from].add(to);
            List[to].add(from);
        }
        int[] parentNode = new int[N+1];
        Queue<Integer> q = new ArrayDeque<>();
        q.add(1);
        visited[1] = true;
        while(!q.isEmpty()){
            int v = q.poll();
            //현재 노드가 트리에 있는지 판별
            for(int i : List[v]){
            	//현재 노드가 트리에 있고 그 노드의 방문 여부 확인
                if(!visited[i]){
                    visited[i] =true;
                    q.add(i);
                    parentNode[i] = v;
                }
            }
        }
        for(int i = 2 ; i< N+1;i++){
            System.out.println(parentNode[i]);
        }
    }

}