BOJ 1761 - 정점들의 거리

문제 링크(Link)

---

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

문제 해결 (Solution)

---

 1. 문제에서 주어지는 그래프가 트리(Tree)임을 알고있다.

 2. 트리에서 두 정점의 거리를 일반적인 방법으로 구하기 위해선 시간복잡도 O(N)이 소요된다. 쿼리의 개수를 고려하면 전체 시간복잡도는 O(NM)이 소요된다. 즉, 400,000,000(4억) 이므로 시간 초과에서 자유로울 수 없다.

 3. dp를 이용한 LCA(최소 공통 조상) 알고리즘을 이용하면 O(logN)만에 두 정점의 거리를 구할 수 있다.(트리에서만...) 

 4. dp[i][j] = 정점 i에서의 2^j 번째 조상.

 5. dist (dist[i] = 루트에서 부터 정점 i 까지의 거리) 라는 배열을 활용해서 두 정점사이의 거리를 구할 수 있다.

 6. 두 정점 i, j 사이의 거리 = dist[i] + dist[j] - 2*dist[LCA(i,j)]

주의할 점 || 생각해볼 점(Caution || Consideration)

---

 -

참고(Reference)

---

 - 아이디어를 받은 Blog : http://jason9319.tistory.com/110

※ 정확하고 부드러운 태클은 언제나 환영입니다.