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

www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

2020-11-12

---

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main11725 {
	public static Queue<Integer> q;
	public static LinkedList<Integer>list[];
	public static boolean vtd[];
	public static int arr[];

	public static void solve() {
		while(!q.isEmpty()) {
			int num = q.poll();
			vtd[num] = true;
			
			for(int i : list[num]) {
				if(!vtd[i]) {
					arr[i] = num;
					q.add(i);
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		list = new LinkedList[N+1];
		vtd = new boolean[N+1];
		arr = new int[N+1];
		q = new LinkedList<Integer>();
		
		for(int i = 0; i <= N; i++) list[i] = new LinkedList();
		
		for(int i = 0; i < N-1; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			list[x].add(y);
			list[y].add(x);
		}
		q.add(1);
		solve();
		
		for(int i = 2; i <= N; i++) {
			System.out.println(arr[i]);
		}
	}
}

 

 

문제는 단순하게 풀었다.

1. LinkedList로 두 개의 이어지는 정점을 저장했다. 

 

2. Queue에 루트 번호를 넣고, 루트와 이어지는 정점들을 돌면서 부모 노드번호를 저장했다.

 

 

맞긴 맞았는데, 메모리와 시간이 너무 커서 초과 날 가능성이 높아 LinkedList가 아닌 ArrayList로 푸는게 더 적절해보인다.