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

 

 

 

입력을 그래프로 처리하고 나면, 리스트에 포함된 첫 번째 원소가 해당 노드의 부모가 된다.

 

트리는 모든 노드가 연결되어있음이 보장되므로, 노드 1부터 시작해 bfs를 돌며 모든 노드의 부모를 찾자.

 

 

 

import java.util.*;
import java.io.*;

public class Main {

    static int N;        

    static int[] parent;
    static ArrayList<Integer>[] list;
    static boolean[] visit;   
    
    static StringBuilder sb = new StringBuilder();
        

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

        N = Integer.parseInt(br.readLine());
            
        list = new ArrayList[N+1];
        parent = new int[N+1];
        visit = new boolean[N+1];
        
        for(int i=1; i<N+1; i++){
            list[i] = 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());
            list[a].add(b);
            list[b].add(a);
        }        

        bfs(1);
        
        for(int i=2; i<N+1; i++){
            System.out.println(parent[i]);
        }

    }

    static void bfs(int start){
        Queue<Integer> q = new LinkedList<>();

        q.add(start);
        visit[start] = true;

        while(!q.isEmpty()){
            int x = q.poll();
            for(int y : list[x]){
                if(visit[y]){
                    continue;
                }
                
                q.add(y);
                parent[y] = x; // 첫 번째 요소가 부모임
                visit[y] = true;
            }
        }
    }
}