[자바] 백준 11812 - K진 트리 (java)

목차

문제 : boj11812

 

 

필요 알고리즘

• 최소 공통 조상 (LCA)
  
  • LCA 문제이다. 근데 몰라도 푸는데 딱히 지장은 없다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  LCA를 안다면 그걸로 바로 접근 가능하고, 몰라도 딱히 상관은 없다. 어차피 첫 깊이엔 1개, 두번째 깊이엔 K개, 세번째 깊이엔 K^2개, ... 의 노드가 존재할꺼다. 그러므로 x와 y를 입력받을 시, K로 나누다보면 점점 부모 노드의 번호를 알 수 있고 결국 루트까지 도달 가능하다.

 

  LCA를 쓴다면 x와 y 중 더 깊이가 높은 쪽을 작은쪽까지 맞춘 후, 두개를 동시에 진행하게 된다. 내 경우엔 굳이 쓰고싶지 않아서 둘 중 깊이가 더 낮은쪽을 그냥 루트까지 진행하면서 만나는 부모노드들의 번호를 모두 찾아둔다. 그 후 더 높은 쪽을 마찬가지로 루트까지 진행하다가, 이미 찾아둔 부모노드들 중 하나를 만난다면 최소 공통 조상을 찾은셈이니 거리를 더해서 출력해주면 된다.

private long getDist(final long n, final int k, final long x, final long y) {
    long hi = x>y?x:y;	// 깊이가 더 높은쪽
    long lo = x>y?y:x;	// 깊이가 더 낮은쪽

    if (k == 1) return hi-lo;

    Map<Long, Integer> exist = new HashMap<>();
    int dist = 0;
    exist.put(lo, dist);	// 우선 깊이가 낮은쪽을 자기자신부터 시작해
    while (lo != 0) {	// 루트까지 부모들을 찾으면서 거리를 재둔다.
        if (lo%k==0) lo = lo/k-1;
        else lo/=k;

        exist.put(lo, ++dist);
    }

    dist = 0;
    while (hi != 0) {	// 이후 깊이가 높은쪽을 진행하다가 위에서 찾아둔 것 중 하나가 나오면
        ++dist;
        if (hi%k==0) hi = hi/k-1;
        else hi/=k;
        if (exist.containsKey(hi))
            return dist+exist.get(hi);	// 그게 최소 공통 조상을 찾은거니 두 거리를 더하면 된다.
    }

    return -1;	// 어차피 루트까지 올라가면 만나므로 여기까지 진행될 일은 없긴하다.
}

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        long n = Long.parseLong(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());

        StringBuilder sb = new StringBuilder();
        while (q-->0) {
            st = new StringTokenizer(br.readLine());
            long x = Long.parseLong(st.nextToken()) - 1;
            long y = Long.parseLong(st.nextToken()) - 1;

            sb.append(getDist(n, k, x, y)).append('\n');
        }

        System.out.print(sb);
    }

    private long getDist(final long n, final int k, final long x, final long y) {
        long hi = x>y?x:y;
        long lo = x>y?y:x;

        if (k == 1) return hi-lo;

        Map<Long, Integer> exist = new HashMap<>();
        int dist = 0;
        exist.put(lo, dist);
        while (lo != 0) {
            if (lo%k==0) lo = lo/k-1;
            else lo/=k;

            exist.put(lo, ++dist);
        }

        dist = 0;
        while (hi != 0) {
            ++dist;
            if (hi%k==0) hi = hi/k-1;
            else hi/=k;
            if (exist.containsKey(hi))
                return dist+exist.get(hi);
        }

        return -1;
    }
}