백준 1761 정점들의 거리 - JAVA

1761 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

 

알고리즘 설명

---

해당 문제는 트리에 존재하는 어떤 두 노드의 거리를 출력하는 문제입니다. 그림을 통해 생각을 해보자면

핑크색 노드(2번 노드)처럼, 두 노드의 거리를 찾기 위해 부모 노드로 거슬러 올라가면서 처음으로 만나게 되는 즉, 최소 공통 조상을 찾아야 하는 문제라고 할 수 있습니다. 이런 문제들을 알고리즘으로 분류하자면 LCA (Lowest Common Ancestor)라고 하는데, 트리 기반 문제에서 핵심이 되는 알고리즘이라고 할 수 있습니다.

 

LCA에 대한 설명 글들은 너무 많고, 질 좋은 글 및 영상들도 많지만 "왜"를 설명하는 글이 많이 없어서... 정리를 해보려고 합니다.

 

자 먼저, 노드가 N개 있는 트리에 대해 최대 깊이를 구해야 합니다. 그런데 최악의 경우인 편향 트리의 경우 깊이가 N까지 늘어나기 때문에, 이를 모두 표현하기 위한 parent[][] 배열의 행의 개수는 높이 N을 커버할 수 있는 N + 1이 되어야 합니다. 하지만 행의 개수를 N + 1개로 저장하게 되면 너무 많은 공간을 사용하기 때문에 트리의 특성인 "루트노드를 제외한 모든 노드의 부모는 하나"인 점을 이용해 '점프 테이블'을 만드는 것입니다.

 

점프 테이블은 각 노드에 대해 2^0, 2^1, 2^2... 처럼 2의 제곱 번째 조상을 기록해두고, 필요할 때 이를 조합해 원하는 상위 노드로 점프할 수 있게 만들어 주는 테이블입니다.

즉, 트리의 깊이가 최악의 경우 N까지 뻗더라도, 2^0 ~ 2^k (2^k ≥ N이 될때까지)처럼 거리를 지수로 늘린 조상 정보만 저장하면 전체 깊이 N을 얼마든지 커버할 수 있는 구조가 만들어 지는 것입니다.

 

이때, k의 최대값을 결정하기 위해 조건을 세우면 다음과 같습니다.

$2^k \ge N$

⬇️ 양변에 log를 취하면 ⬇️

$k \ge \log_2(N)$

⬇️ k를 LOG로 바꾸고 코드에서 LOG의 값을 정수형으로 반올림하면 ⬇️
LOG = (int) Math.ceil(Math.log(N) / Math.log(2))

따라서 parent[][] 배열의 행의 높이는 0부터 LOG까지 즉, LOG + 1이 되는 것 입니다.

 

이제 parent[][] 배열의 크기를 정했으니, 본격적으로 트리 정보를 채우는 단계로 넘어가보겠습니다.

 

먼저 dfs() 메서드 입니다. 해당 메서드는 루트로부터 얼마나 떨어져있는지를 기록할 depth[] 배열과, 루트로부터 가중치를 기록할 dist[] 배열을 채우고, tree리스트를 활용하여 각 노드의 첫 번째 부모를 parent[0][node]에 채우는 역할을 합니다.

먼저 노드 1을 루트노드로 설정하고, tree[1]내의 원소(v)들을 시작으로

1. depth[v] = depth[node] + 1 과 같이 루트 노드로부터 얼마나 떨어져 있는지를 계산
2. dist[v] = dist[node] + weight와 같이 루트노인 1로 부터의 깊이 및 거리(가중치)를 모두 계산
3. 각 노드의 부모 노드를 parent[0][node]에 계산

위 3가지를 재귀적으로 모든 노드를 방문하여 값을 채워 넣습니다.

 

이제 채워진 parent[0]을 기반으로 나머지를 채울 buildParent() 메서드를 살펴보겠습니다. DFS로 채운 parent[0][node]는 각 노드의 바로 위 부모만을 알고 있지만, 바이너리 리프팅에서는 2칸, 4칸, 8칸... 위의 조상도 필요합니다.

이번 방식도 재귀적 계산 방식을 활용할텐데,

i번째 node의 2^k 번째 조상 노드를 찾기위해, 2^(k-1) 번째 조상을 먼저 찾고, 그 조상의 2^(k-1) 번째 조상을 다시 찾으면 i번째 node의 2^k 번째 조상이 됩니다. 설명만 보면 어려울 수 있으니 아래 트리를 예시로 간단한 예를 들어보겠습니다.

 

노드 8의 2^1번째 조상을 찾는다고 생각해보겠습니다.

parent[k][i] = parent[k - 1][parent[k - 1][i]];

그러면 위의 코드대로 parent[1][8] = parent[0][parent[0][8]]이 될것 입니다.

정리해보면 parent[0][8]은 4이므로 parent[1][8] = parent[0][4]가 될 것입니다. 위의 트리를 보면서 이해하니 어느정도 감이 잡힐 것이라고 생각합니다. (제가 이 부분이 제일 어려웠습니다...)

 

+ 저를 위해, 아직 이해를 못하신 분들을 위해 점프 테이블인 parent[][] 배열에 어떤 원소가 저장될지 시각화 해보겠습니다.

parent[][] 배열 (굵은 선 내부가 실제 원소가 저장되어있는 부분)

이제 완성된 depth[] 배열, parent[][]을 가지고 두 노드의 최소 공통 조상(LCA) 노드를 구할 수 있는데, 해당 부분은 findLca() 메서드에 정의해 놓았습니다.

먼저 두 노드 a와 b의 깊이를 맞춥니다. 깊이가 더 깊은 노드를 a로 설정하고 두 노드의 depth차이를 맞추기 위해 b와 같은 레벨의 a의 부모를 찾습니다.

이때, 비트연산자를 사용하지 않고 아래와 같이 코드를 짤 수 도 있습니다.

while (depth[a] > depth[b]) {
    a = parent[0][a]; // 한 칸씩 위로 올라감
}

위 코드는 바로 위 부모 노드를 찾아 올라가기 때문에 코드가 직관적이라는 장점이 존재하지만(장점 맞나...), 깊이 차이가 큰 즉, diff가 큰 경우 diff만큼 반복을 해야하기 때문에 시간복잡도가 O(N)으로 고정되는 단점이 존재합니다.

따라서 비트연산자를 활용한 바이너리 리프팅(Binary Lifting)을 활용하여 빠르게 계산합니다.

 

for (int k = 0; k <= LOG; k++) {
    if ((diff & (1 << k)) != 0) {
        a = parent[k][a];
    }
}

바이너리 리프팅은 k = 0부터 트리의 최대 깊이인 LOG까지 반복하며 두 노드의 깊이 차이인 diff의 k번째 비트가 1인지 확인하는 연산입니다. k번째 비트가 1이면 노드 a를 2^k만큼 한 번에 위로 점프시킵니다.

예를 들어 diff가 7이라면 diff는 0111(2)이 되므로 a노드는 1만큼 위로 -> 2만큼 위로 -> 4만큼 위로 올라갈 수 있는 것입니다. 그러면 마치 이분탐색과 같이 빠르게 탐색 할 수 있으며 이분탐색(BinarySearch)과 동일하게 O(logN)의 시간복잡도를 가집니다.

 

반복 횟수만 봐도 트리의 깊이가 깊어질수록 훨씬 효율적인 방식인 것을 알 수 있습니다. 알아두면 꽤나 유용한 알고리즘이 될 것 같습니다. 두 노드의 높이를 맞췄다면, k = LOG부터 줄여가며, parent[k][a]와 parent[k][b]가 될 때까지, lca를 찾아갑니다.

 

결국, 점프 테이블을 활용한 LCA 탐색에서 핵심 원리이자 효율성을 보장하는 방법이 바로 바이너리 리프팅이라고 할 수 있습니다.

 

일부러 늦게 말씀드렸지만, 이렇게 바이너리 리프팅을 사용한 LCA 알고리즘을 "개선된 LCA 탐색" 방식이라고 합니다. 아래는 일반 lca와 개선된 lca의 소요시간 차이입니다.

위부터 차례대로 개선된 LCA, LCA

 

이제, 공통된 두 노드의 조상을 찾았다면 두 노드의 거리를 찾기만 하면 끝납니다. 아래 그림과 함께 설명드리겠습니다.

그림을 기준으로 u노드에서 v노드의 거리를 구해야 합니다. 하지만 dist[] 배열은 루트노드를 기준으로 각 노드까지의 거리만을 저장하고 있기 때문에, depth[u]와 depth[v]를 더하고, 겹치는 depth[lca]를 두 번 빼주면 그 값이 노드u 부터 노드v 까지의 값임을 알 수 있습니다. 코드는 아래와 같습니다.

int answer = dist[a] + dist[b] - 2 * dist[dis];

 

트러블 슈팅🚀

---

뭐 별거 아닐 수 있지만, 저는 왜 k를 큰 값부터 줄여가며 LCA를 찾아야 하는지가 처음에는 바로 와닿지 않았습니다.

 

예를 들어, 깊이가 맞춰진 두 노드의 LCA까지의 거리가 4라고 가정해보겠습니다.

 

• 만약 k = 0부터 탐색을 시작하면, 2^0, 2^1… 순으로 작은 단위 점프를 계속 시도하게 됩니다.
• 이때 점프를 1 + 2 + … 형태로 누적해야 LCA 노드까지 도달할 수 있는데, 정확히 4칸을 한 번에 만들 수 없기 때문에 원하는 LCA노드에서 멈추지 못할 수 있습니다.

 

반대로, k = LOG부터 큰 값부터 점프하면

 

• 먼저 가능한 가장 큰 단위(2^k)로 점프
• 그 다음 작은 단위로 조정(...4 + 2 + 1)

 

이렇게 하면 한 번에 최대한 위로 점프하면서도, 정확히 LCA 직전 단계에서 멈출 수 있습니다. 아래 그림으로 간단하게 표현해보겠습니다.

[ k = 0부터 k를 늘려가며 탐색하는 경우 찾게되는 LCA ] 와 [ k = LOG부터 k를 줄여가며 탐색하는 경우 찾게되는 LCA ]

 

 

코드 해석

---

인접리스트 tree를 만들고, N 만큼 tree정보를 입력받아 양방향으로 저장합니다.

양방향으로 저장하는 이유는 트리의 부모-자식 방향을 모르는 상태에서도 DFS를 통해 모든 노드를 정확히 탐색할 수 있기 때문입니다.

DFS를 돌면서 if (v == par) continue; 조건으로 부모 방향을 건너뛰면, 루트 노드 어디에서 시작하든 자식 노드만 방문하게 되어 안전하게 트리 구조를 초기화할 수 있습니다.

 

그 후, DFS를 이용해 각 노드의 깊이를 기록하는 depth[] 배열과, 루트로부터 누적 가중치를 계산하는 dist[] 배열을 채우고, 각 노드의 첫 번째 부모를 parent[0][node]에 저장합니다.

 

그 후, DFS를 이용해 각 노드의 깊이를 기록하는 depth[] 배열과, 루트로부터 누적 가중치를 계산하는 dist[] 배열을 채우고, 각 노드의 첫 번째 부모를 parent[0][node]에 저장합니다.

 

이후 buildParent()로 2^k 번째 조상 정보를 채워 점프테이블 구성하고, findLca(a, b)로 a노드와 b노드의 깊이 level을 맞춰 lca를 k = LOG부터 동일한 노드가 나올 때까지 반복 진행하고, 반환된 lca 노드를 dist[] 배열을 사용해 두 노드간의 거리를 구한 후 반환합니다.