[BOJ] 1761 정점들의 거리 (C/C++)

1761번: 정점들의 거리

문제

N(2 ≤ N ≤ 40,000)개의 정점으로 이루어진 트리가 주어지고 M(1 ≤ M ≤ 10,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

입력

첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 입력된다. 두 점 사이의 거리는 10,000보다 작거나 같은 자연수이다.

정점은 1번부터 N번까지 번호가 매겨져 있다.

출력

M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다.

---

LCA 문제를 오랜만에 풀었다. 사실 문제에서 트리라는 언급이 없었으면 LCA가 바로 떠오르지 않았을 것이다. 정점들의 거리라는 문제 이름만 보면 다익스트라로 가지 않았을까. 모든 그래프가 트리는 아니라서 정점 사이 거리를 구하는 데에 무턱대고 LCA를 사용할 수는 없지만, 그래프가 트리라고 특정되어 있는 상황이라면 LCA도 적용할 수 있다는 것을 알게 됐다. 이 문제에서는 입력받을 때 두 노드 사이 거리가 주어지고, 트리에서 두 점 사이의 거리를 구하기 위해선 루트에서 각 정점 사이의 거리 합에서 두 점의 공통 조상의 거리를 두 번 빼면 된다. 

 

세그먼트 트리처럼 LCA도 오랜만이라 정확히 기억이 나질 않았다. 이전에 포스팅했던 문제를 참고했다. 두 점 사이 거리를 구하기 위해서 dist 배열을 추가한 것 빼고는 거의 같았다. 어차피 트리라서 어떤 점을 루트로 하는 지는 크게 상관없기 때문에 그냥 1번 노드를 루트로 설정했다. 각 노드의 깊이를 구하고, 바로 위의 부모를 이용해서 더 위의 부모를 구해놓는다. 

 

입력이 들어올 때마다 공통 조상을 구해서 두 점 사이의 거리를 계산한다. 

 

 

후기)

오랜만에 LCA를 푼거라서 기억이 잘 안 났다. 백준에서만 4번째 문제인 것 같은데 매번 이런 식으로 오랜만에 풀면 기억이 잘 안 난다.