[백준] 11725 : 트리의 부모 찾기 JAVA 풀이

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

public class Main {

	static class Node{
		int data;
		Node left;
		Node right;
		
		Node(int data){
			this.data = data;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		// 양방향그래프
		ArrayList<ArrayList<Integer>> list = new ArrayList<>();
		
		for(int i=0;i<N;i++) {
			list.add(new ArrayList<>());
		}
		
		for(int i=0;i<N-1;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			int A = Integer.parseInt(st.nextToken())-1;
			int B = Integer.parseInt(st.nextToken())-1;
			
			// 두 정점을 양방향 연결
			list.get(A).add(B);
			list.get(B).add(A);
		}
		
		// 해당 노드를 방문했는지 검사하는 배열
		boolean[] visit = new boolean[N];
		// 부모를 저장하는 배열
		int[] parent = new int[N];
		
		// bfs를 하기 위한 큐
		Queue<Integer> queue = new LinkedList<>();
		// 루트노드를 큐에 넣고 방문했다고 체크
		queue.add(0);
		visit[0] = true;
		
		// 큐가 빌 때까지 반복
		while(!queue.isEmpty()) {
		// 큐에서 꺼낸 값을 v에 저장
			int v = queue.poll();
            
			// v의 인접 정점들에 대해서 반복함
			for(int node : list.get(v)) {
				// 아직 방문하지 않았다면
				if(!visit[node]) {
					// 방문했다고 표시하고 큐에 넣은 뒤,
					// 부모 노드의 정보를 배열에 저장
					visit[node] = true;
					queue.add(node);
					parent[node] = v;
				}
			}
		}
		
		// 부모 노드를 출력
		for(int i=1;i<N;i++) {
			System.out.println(parent[i]+1);
		}
	}

}