[BOJ] 11725 트리의 부모 찾기

11725 트리의 부모 찾기

난이도 : 실버 2
유형 : 트리

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

문제

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

입력

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

출력

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

풀이

양방향 연결이 핵심인 것 같다.

코드

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

/**
 * BOJ_11725_S2_트리의 부모 찾기
 * @author mingggkeee
 * 트리
 */

public class BOJ_11725 {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine()); // 노드의 수 받기
		List<Integer> list[] = new ArrayList[N+1]; 
		
		// 리스트의 배열을 만들기 위한 작업
		for(int i=0; i<list.length; i++) {
			list[i] = new ArrayList<>(); // 여러가지 자식노드를 받기 위함.
		}
		
		for(int i=0;i<N-1;i++) {
			st = new StringTokenizer(br.readLine());
			int num1 = Integer.parseInt(st.nextToken());
			int num2 = Integer.parseInt(st.nextToken());
			// 서로 연결되어 있기 때문에 각각 추가
			list[num1].add(num2);
			list[num2].add(num1);
		}
		
		boolean isVisited[] = new boolean[N+1];  // 방문처리 배열
		
        // 부모찾기
		Queue<Integer> queue = new LinkedList<Integer>();
        // 루트부터 시작
		queue.add(1);
		isVisited[1] = true;
		
		int answer[] = new int [N+1];	// 부모값을 넣어줄 배열 
		while(!queue.isEmpty()) {
			int num = queue.poll();
			for(int i : list[num]) { // 자식들 훑기
				if(!isVisited[i]) {
					isVisited[i] = true;
					answer[i] = num;	// i 의 부모는 num
					queue.add(i);
				}
			}
		}
		for(int i=2; i<answer.length; i++) {
			System.out.println(answer[i]);
		}
	}
}