wwiiiii   2년 전

   제가 아는 건 두 노드에서 루트까지 올라가는 경로를 따로 저장하고, 루트에서부터 내려가면서 처음으로 달라지는 점 바로 앞의 노드가 최저 공통 조상이 되므로 이렇게 찾는 방법만 아는데 다른 효율적인 알고리즘이 있나요?

baekjoon   2년 전

가장 간단한 알고리즘으로 각 노드의 parent와 depth를 저장하는 방법이 있습니다.

찾으려고 하는 두 노드를 u와 v라고 한다면, 두 노드의 depth가 같아질 때 까지 parent로 이동합니다.  (아래 1번 소스)

그 다음 두 노드가 같아질 때 까지 u와 v를 parent로 이동시킵니다.

이 방법을 바탕으로 루트를 사용하는 방법과 log2를 사용하는 방법 두 가지가 더 있습니다.

http://community.topcoder.com/tc?module=Static&d1=...

august14   2년 전

O(lg N) 만에 찾는법을 설명하자면 각 노드에 대해 2^i번 위로 올라갔을때의 조상을 저장하는 겁니다. 



노드 v에 대해서 p[v,i] = 2^i번 위로 올라갔을때의 조상

이라고 하면

p[v,i+1] = p[p[v,i],i]

이므로 우선 O(N lg N)만에 전처리가 가능합니다.

그리고 위에서 백준님이 설명한 루프를 모두 O(lg N) 만에 해내면 됩니다.

1번 루프는 뎁스 차이를 이진수로 만들어서 올라가면 되고

2번 루프는 높은 i에서부터 내려오면서

p[u,i] != p[v,i] 면 u = p[u,i]   v = p[v,i]로 갱신하다가 마지막에 한번 위로 올려주면 됩니다.

댓글을 작성하려면 로그인해야 합니다.