백준 11725번

트리의 부모 찾기

문제

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

입력

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

출력

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

예제

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 트리
• 너비 우선 탐색
• 깊이 우선 탐색

코드

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

public class Main {
	public static int N;
	public static int S;
	public static int answer = 0;
	public static int arr[];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		boolean visited[] = new boolean[N+1];
		int result[] = new int[N+1];
		
		List<Integer> list[] = new ArrayList[N+1];
		Queue<Integer> queue = new LinkedList<Integer>();
		
		for(int i=0; i<list.length; i++) 
			list[i] = new ArrayList<Integer>();
		
		for(int i=0; i<N-1; i++) {
			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);
		}
		
		queue.add(1);
		visited[1] = true;
		
		while(!queue.isEmpty()) {
			Integer num = queue.poll();
			
			for(Integer i : list[num]) {
				if(!visited[i]) {
					visited[i] = true;
					result[i] = num;
					queue.add(i);
				}
			}
		}
		
		for(int i=2; i<result.length; i++)
			System.out.println(result[i]);
	}
}

풀이

처음에는 문제를 이해를 잘 못했는데, 그냥 트리 형태를 그림판에 그려서 보니 이해가 됬다.
List<>[] 리스트와 배열을 합해서 트리를 작성한다.
루트값이 1임을 활용하면 된다. >
queue를 활용하는 BFS 방식을 사용했다.