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

문제

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

입력

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

출력

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

예제 입력 1 복사

7
1 6
6 3
3 5
4 1
2 4
4 7

예제 출력 1 복사

4
6
1
3
1
4

예제 입력 2 복사

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

예제 출력 2 복사

1
1
2
3
3
4
4
5
5
6
6

 

※코드

 

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

public class Main {
	static boolean [] visited;
	static int N, v, w;
	static List<Integer> [] node;
	static int [] dap;
	public static void BFS(int start) {
		Queue<Integer> q = new LinkedList<Integer>();
		// 시작노드 방문
		visited[start] = true;
		// 큐에 시작노드 담기
		q.offer(start);
		
		// 큐에 값이 없을 때까지 반복
		while(!q.isEmpty()) {
			start = q.poll();
			for(Integer i : node[start]) {
				if(!visited[i]) {
					visited[i] = true;
					dap[i] = start;
					q.offer(i);
				}
			}
		}
		for(int i = 2; i <= N; i++) {
			System.out.println(dap[i]);
		}
		
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		int limit = N-1;
		node = new ArrayList[N+1];
		dap = new int[N+1];
		for(int i = 0; i <= N; i++) {
			node[i] = new ArrayList<>();
		}
		visited = new boolean[N+1];
		
		while(limit > 0) {
			st = new StringTokenizer(br.readLine());
			
			/* node input */
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			node[v].add(w);
			node[w].add(v);
			
			limit--;
		}
		BFS(1);
	}

}

 

BFS를 이용해 푼 문제 큐에 저장된 숫자가 빠져나갈때의 값을 저장해두고 해당 노드를 방문할때 배열값에 부모노드의 숫자를 넣어준다

 

-새벽코딩-