[백준] 11812번: K진 트리

문제링크 : https://www.acmicpc.net/problem/11812

 

문제풀이

처음엔 DFS로 풀으려고 했는데, 부모노드까지 갔다가 되돌아 오는 작업이 생각보다 복잡했다.

 

LCA 알고리즘 분류에 속한다고 적혀있어서 알고리즘을 찾아보았다.

LCA 알고리즘이란 공통 조상을 찾는 알고리즘을 말한다.

 

즉 입력받은 각 두 노드가 공통된 조상을 가질 때 까지 이동한 거리를 합하면, 두 노드 사이의 거리가 된다.

그러면 먼저 각 노드의 부모 노드를 구해야 하는데, 부모 노드의 번호는 다음 공식으로 구할 수 있다.

이 공식을 이용하여, 두 노드의 부모가 같아질 때 까지 거리를 증가시키면 된다.

위와 그림과 같은 경우 거리는 4가 된다.

7 → 2 → 1 (거리 : 2)

8 → 3 → 1 (거리 : 2)

 

---

 

1. 코드를 작성하여 백준에 제출하였더니 런타임에러가 났다.

문제를 다시 보니 N의 범위가 10¹⁵였다. long형으로 고치면 된다.

 

2. 다시 제출을 했더니 이번엔 시간초과가 떴다..

N이 98765432111이고 K가 1인 경우 반복문은 98765432110번이나 돌게 된다.

따라서 K가 1인 경우, 부모를 따로 계산할 필요 없이 결과가 N - 1이므로 별도로 처리를 해준다.

 

소스코드

package baekjoon;

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

public class P11812 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		StringTokenizer st = new StringTokenizer(str);
		
		long N = Long.parseLong(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int Q = Integer.parseInt(st.nextToken());
		
		for (int i = 0; i < Q; i++) {
			str = br.readLine();
			st = new StringTokenizer(str);
			long x = Long.parseLong(st.nextToken());
			long y = Long.parseLong(st.nextToken());
			
			long count = 0;
			if (K == 1) {
				count = x < y ? y - x : x - y;
			}
			else {
				while (x != y) {
					// 부모 노드
					if (x < y) {
						y = (y - 2) / K + 1;
					}
					else {
						x = (x - 2) / K + 1;
					}
					
					count++;
				}
			}			
			
			System.out.println(count);
		}
	}
}