백준 25511번: 값이 k인 트리 노드의 깊이

문제 설명

• https://www.acmicpc.net/problem/25511
• 주어진 트리에서 k번 노드의 깊이를 구하는 문제입니다.

접근법

• unoin-find에서 부모를 찾는 findParent메서드를 변형했습니다.
  findParent에 depth변수를 추가합니다. 재귀를 실행할 때 마다 depth를 1 늘리고 parent값이 아닌 depth를 return 합니다.

정답

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

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int[] parent = new int[n];
		for (int i = 0; i < n-1; i++) {
			st = new StringTokenizer(br.readLine());
			int p = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			parent[c] = p;
		}
		parent[0] = -1;
		int[] arr = new int[n];
		st = new StringTokenizer(br.readLine());
		int target = 0;
		for (int i = 0; i < arr.length; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			if(arr[i] == k) {
				target = i;
			}
		}
		System.out.println(depthToRoot(target,0,parent));
		
	}
	public static int depthToRoot(int x, int depth, int[] parent) {
		if(parent[x] == -1) return depth;
		return depthToRoot(parent[x],depth+1,parent);
		
	}
}