루트 노드가 정해진 트리에서 부모 - 자식 관계를 O(1)에 구하는 법

루트 노드가 정해진 트리에서 두 노드의 부모 - 자식 관계를 확인할 때 여러 방법이 있다.

 

v는 정점(vertext) e는 간선(edge)이다.

 

일단 간단하게 한 노드에서 BFS를 진행하여 루트 노드까지 탐색하는 경우로 이 경우에는 미리 루트 노드에서 탐색을 진행하여 루트 노드로부터의 거리값을 알고 있어야 더 수월하게 진행된다. 시간복잡도는 루트 노드에서의 탐색 O(V+E) + 한 노드에서의 탐색O(V+E)이다.

 

위의 방법을 조금 발전시키면 그것이 최소 공통 조상 즉 LCA(least common ancestor) 알고리즘이다. LCA 알고리즘의 대략적인 흐름은 루트노드까지의 거리를 구해 놓고 거리가 먼 쪽을 이동시켜 거리가 같도록 맞춰준다. 그 다음부터 두 노드를 한 칸씩 이동시키고 그리고 높이가 같아지면 루트노드까지 거슬러 올라가면서 부모 - 자식 관계를 확인할 수 있다. 왜냐하면 사실 맨 처음 높이를 맞출 때 높이가 같아졌을 때 그 값이 같다면 그게 곧 부모 자식 관계임을 증명하는 것이다. (union-find의 find와 비슷한 원리) 이 떄의 시간복잡도는 루트노드로부터의 거리를 구하기 위한 1차 탐색 O(V+E) + LCA 알고리즘 O(V) 이다.

 

조금 복잡하고 여기서는 설명하지 않겠지만 분할정복을 이용한 거듭제곱과 비슷한 원리로 깊이차이가 예를 들어 깊이차이가 5면 4칸 올라가고 1칸 올라가고 , 6이면 4칸 2칸 이런식으로 2의 거듭재곱 만큼씩 올라가는 방식으로 최적화 해줄 수 있다. 이런 식으로 최적화된 LCA 알고리즘을 이용할 수도 있다. 분할정복을 이용한 거듭제곱과 마찬가지로 시간복잡도는 O(logN)이다. 따라서 이 경우 루트 노드로부터 거리 O(V+E) + 최적화된 LCA 알고리즘 O(lg V) 이다.

 

문제는 여기서 발생한다. 해당 알고리즘을 적용한다 한들 query의 개수가 50만개, 100만개라면 시간초과가 발생하게 된다.

앞서 말한 경우 아무리 빨라도 query의 개수 만큼 탐색을 반복해야 하므로 O(V+E+q*(lg V)) 만큼의 시간복잡도를 갖게 된다.

 

사실 이 문제는 DFS 1번으로 풀 수 있다. DFS를 진행할 때 들어가는 시간과 나가는 시간을 저장해준다. 그리고 만약 두 노드가 A노드에 진입한 시간 < B노드에 진입한 시간 < B 노드에서 탈출한 시간 < A노드에서 탈출한 시간 이라면 B노드는 A노드의 자식 노드인 것이다. 시간만 알고있으면 되므로 O(1) 의 시간복잡도로 부모 자식 관계를 해결할 수 있다. 따라서 쿼리가 많다 하더라도 DFS 1번 O(V+E) + 1*Q이므로 O(Q) 총 O(V+E+Q) 의 시간복잡도로 해결이 가능하다.