Baekjoon 11725 트리의 부모 찾기 JAVA

11725번: 트리의 부모 찾기

문제

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

입력

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

출력

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

풀이

반례

4

1 2

4 3

3 2

 

입력 받아지는 두 정점으로는 부모 관계를 알 수 없기에 양방향으로 간선을 그려준다.

이때 노드의 개수는 100000개 이므로 행렬을 이용한다면 10000000000으로 시간초과가 뜨기에 리스트를 이용한다.

모든 노드를 입력받고, 전체 트리의 루트는 1이라고 했으므로, 1부터 전체연결된 간선들을 검사하면서, 그에 대한 연결된 형태로 부모간선을 찾아준다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

	static ArrayList<ArrayList<Integer>> arr = new ArrayList<ArrayList<Integer>>();
	static int [] ans;
	public static void dfs(int loc) {
		for(int k : arr.get(loc)) {
			if(ans[k]==0) {
				ans[k]=loc;
				dfs(k);
			}
		}
	}	
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		ans=new int [n+1];
		for(int i=0;i<=n;i++)
			arr.add(new ArrayList<>());
		for (int i = 0; i < n - 1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()), b = Integer.parseInt(st.nextToken());
			arr.get(a).add(b);
			arr.get(b).add(a);
		}
		dfs(1);
		
		for (int i = 2; i <= n; i++)
			bw.write( ans[i]+"\n");
		bw.close();
	}
}