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

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

 

 

조건

• TimeLimit = 1s
• 노드 수 (2<=N<=10만)
• 트리의 루트는 1이다
• 각 node의 부모를, 2번부터 n번까지 순서대로 출력하여라

 

풀이

• n이 10만이지만, BFS를 사용하면 depth 한번만 돌면 된다. 따라서 O(10만)으로 가능
  • 양방향으로 연결
  • 1부터 BFS를 시작
  • parent = new int[n+1]로 부모를 저장해두자

 

코드

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


public class Main {

	static StringTokenizer st;
	static int n;
	static List<Integer>[] edge;
	static int[] parent;
	static boolean[] visited;
	
	public static void main(String[] args) throws IOException {

		// input
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		
		n = Integer.parseInt(br.readLine());
		
		edge = new ArrayList[n+1];
		for (int i=1; i<n+1; i++) edge[i] = new ArrayList<>();
		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());
			
			edge[a].add(b);
			edge[b].add(a);
			
		}
		
		// bfs
		parent = new int[n+1];
		visited = new boolean[n+1];
		bfs();
		
		// result
		StringBuilder sb = new StringBuilder();
		for (int i=2; i<n+1; i++) sb.append(parent[i]).append("\n");
		
		System.out.print(sb);
	}
	
	
	
	static void bfs() {
		
		Deque<Integer> q = new ArrayDeque<>();
		q.add(1);
		
		while (!q.isEmpty()) {
			
			int cur = q.pop();
			visited[cur] = true;
			
			for (int child : edge[cur]) {
				
				if (visited[child]) continue;
				
				parent[child] = cur;
				q.add(child);
				
			}
		}
	}
	
	
}