글 읽기 - 트리에서 최저 공통 조상 찾는 알고리즘

wwiiiii 10년 전 0

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

baekjoon 10년 전 3

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

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

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

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

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

// 1: depth가 같아질때까지
while (depth[u] > depth[v]) u=parent[u];
while (depth[v] > depth[u]) v=parent[v];

// 2: parent로 이동
while (u != v) {
	u = parent[u];
	v = parent[v];
}

august14 10년 전 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]로 갱신하다가 마지막에 한번 위로 올려주면 됩니다.

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

문제

문제

출처

ICPC

트리에서 최저 공통 조상 찾는 알고리즘

wwiiiii 10년 전 0

baekjoon 10년 전 3

august14 10년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말