[BOJ] 11725 트리의 부모 찾기 (JAVA)

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

11725번: 트리의 부모 찾기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int N;
	static int[] parent;
	
	public static void main(String[] args) throws IOException {
		
		N = Integer.parseInt(br.readLine());	// 정점 수
		parent = new int[N + 1];
		parent[1] = 1;
		
		for (int i = 1; i < N; i++) {
			
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			if(parent[a] != 0 && parent[b] != 0) {
				if(one(b)) {
					reverse(a);
					parent[a] = b;
				}else {
					reverse(b);
					parent[b] = a;
				}
			}
			else if(a == 1) parent[b] = a;
			else if(b == 1) parent[a] = b;
			else if(parent[a] != 0) parent[b] = a;
			else if(parent[b] != 0) parent[a] = b;
			else parent[b] = a;
			
		}
		
		for (int i = 2; i <= N; i++) sb.append(parent[i]).append("\n");
		
		System.out.println(sb);
		
	}
	
	// 조상 중 1이 있으면 true 반환
	static boolean one(int a) {
		
		if(parent[a] == 1) return true;
		else if(parent[a] == 0) return false;
		
		return one(parent[a]);
		
	}
	
	// n의 부모, 부모의 부모, ... 을 모두 n의 자식, 자식의 자식, ... 으로 바꿈
	static void reverse(int n) {
		
		int p = parent[n];
		
		if(parent[p] != 0) reverse(p);	
		
		parent[p] = n;
		
	}
	
}