[Giraffe] Lowest Common Ancestor
왜 플래티넘 문제인 줄 알겠다.
본 문제를 트리 알고리즘인 것은 맞으나, 일반적인 트리의 형태를 갖는 알고리즘으로 푼다면 100% 실패할 것이다. 왜냐하면 주어지는 형태가 트리가 아닌 그래프 형태이기 때문이다.
모든 트리는 그래프이다. 따라서 해당 문제는 주어지는 그래프 형태를 후향적으로 트리형태로 바꾸어주는 변환과정이 필요하며, 이에 기본적인 데이터 틀은 그래프 형태로 만들되, 추가적으로 트리형태를 갖추기 위한 몇가지의 변수가 추가되어야 한다.
우리말로 최소 공통 조상이라고 한다. 굉장히 어려운 말처럼 보이지만, 두 노드가 있다고 할 때 가장 가까운 공통으로 갖는 조상이 무엇인지 찾는 문제이다. 두 노드의 첫 분기점을 찾는 문제라 볼 수 있겠다.
기본적으로는 트리 문제이기 때문에 Bottom Up, Top Down 모두 생각해 볼 수 있으나, 트리라는 데이터 구조 특성 상, 아래로 가면 데이터가 많아지고 위로 가면 데이터가 1에 수렴하기 때문에, 자식에서 부모쪽으로 가도록 설계하는 것이 해당 예시에서 바람직 할 것이다. (그렇지 않으면 두 노드를 찾기 위해 모든 노드를 뒤져야 할 것이니)
다행이도 찾으려는 두 노드는 이미 주어진다. 노드의 값의 형태로 주어지기 때문에, 인덱스를 데이터로 지정하여 노드를 O(1)시간에 찾을 수 있는 배열의 형태의 저장이나, 해시를 통해 저장하는 형태가 바람직할 것이다.
해당 알고리즘은 약 가지 연산이 필요하다.
해당 문제의 어려운 이유는 위에 있는 부분 때문이다. 그래프 형태로 트리를 구현해야 하는 이유이기도 한데, 위 사진처럼 두 노드만 주어진다고 했지 어느 노드가 조상 노드인지는 밝히고 있지 않다. 따라서 a, b노드가 연결되어 있음을 알고 있더라도, 어떤 노드가 조상인지 알 수 있는 시점은 트리가 모두 만들어지고 난 시점에서의 확인 작업을 통해 알 수 있게 되는 것이다. 또한 이진트리라고 하고 있지도 않기 떄문에 일반적인 트리형태로 구사하여야 하며, 이에 가장 가까운 초기 자료형태는 트리가 아닌, 그래프 형태가 맞게되는 것이다.
그렇다면 어떻게 알 수 있을까?
다행이도 해당 문제에서는 루트노드가 1번임을 알려주고 있다. 만약 이 조건이 없었더라면 루트 노드가 여러개가 생길 수도 있고(자식이 1개밖에 없는 몇몇의 조건 하에서), 모든 정점에 대해 트리가 성립하는지 검증하는 절차를 추가해야한다. 따라서 정말 까다로운 문제가 될 수 있었던 문제일 것이다.
다만 1번 노드가 루트노드이기 때문에 DFS시작 기준을 1번 노드로 삼아 탐색해가며 노드의 depth를 정립해주면 된다.
트리를 순회하는 방식은 여러가지가 있겠지만, 트리와 그래프를 동시에 순회할 수 있는 방식은 많지 않다. 해당 위키에서는 DFS를 기준으로 그래프를 탐색해가며 부모노드를 결정할 것이다. DFS는 깊이를 우선으로 재귀적으로 그래프를 순회하는 방식으로 비슷한 방식인 BFS(너비 우선 탐색)알고리즘에 비해 구현이 간단한 장점이 있다. (시간 복잡도는 같다)
그냥 두 노드를 바로 거슬러 올라오기만 한다면 문제가 생긴다.
바로 두 노드의 depth가 다른 경우인데, 1번 루프가 돌 때마다 depth는 1씩 내려오게 됨으로(부모 노드를 향해), depth가 더 낮은 쪽을 기준으로 탐색 노드를 맞추어주어야 한다. 당연히 두 노드 사이의 depth 사이에는 공통 조상이 있을 수 없다. (조상의 뜻을 생각해보면 쉽게 알 수 있다.)
다 됐다면 이제 추가해줄 작업은 간단하다 간단한 루프를 통해 조상이 같아질 때까지 탐색 노드가 부모 노드를 향해 올라가도록 구현하는 것이다.
N = int(sys.stdin.readline()) # 노드 수
depth = [0] * (N + 1) # 노드별 깊이 정보
parent = [0] * (N + 1) # 노드 별 부모 정보
visited = [False] * (N + 1) # dfs시 노드 방문 정보
graph = [[] for _ in range(N + 1)] # 그래프 정보 (인접 리스트 기반)
for _ in range(N - 1): # 그래프 초기화
a, b = map(int, sys.stdin.readline().split())
# 무향 그래프이므로, 양방향에 초기화 해야한다.
graph[a].append(b)
graph[b].append(a)def dfs(node: int, d: int):
# 깊이 설정 (현재노드)
depth[node] = d
visited[node] = True
# 자식 노드의 부모 설정
for adj_node in graph[node]:
if not visited[adj_node]:
parent[adj_node] = node
dfs(adj_node, d + 1) # 노드의 깊이는 1번이 더 작게 설정
if depth[node_1] > depth[node_2]:
node_1, node_2 = node_2, node_1
# 두 노드의 depth 맞추기
while depth[node_1] != depth[node_2]:
node_2 = parent[node_2] while node_1 != node_2:
node_1 = parent[node_1]
node_2 = parent[node_2]
return node_1import sys
def dfs(node: int, d: int):
# 깊이 설정 (현재노드)
depth[node] = d
visited[node] = True
# 자식 노드의 부모 설정
for adj_node in graph[node]:
if not visited[adj_node]:
parent[adj_node] = node
dfs(adj_node, d + 1)
def lca(node_1, node_2):
# 노드의 깊이는 1번이 더 작게 설정
if depth[node_1] > depth[node_2]:
node_1, node_2 = node_2, node_1
# 두 노드의 depth 맞추기
while depth[node_1] != depth[node_2]:
node_2 = parent[node_2]
while node_1 != node_2:
node_1 = parent[node_1]
node_2 = parent[node_2]
return node_1
N = int(sys.stdin.readline())
depth = [0] * (N + 1)
parent = [0] * (N + 1)
visited = [False] * (N + 1)
graph = [[] for _ in range(N + 1)]
for _ in range(N - 1):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
dfs(1, 1)
M = int(sys.stdin.readline())
for _ in range(M):
a, b = map(int, sys.stdin.readline().split())
print(lca(a, b))
젠장 시간초과다.
상당히들 하고 있는 트리 알고리즘의 "착각"이 있다.
트리 알고리즘은 log(N)의 알고리즘을 갖는다는 것이 바로 그것인데, 트리 알고리즘이 효율적이라는 착각이다.
트리 알고리즘은 대다수의 경우 log(height)의 시간복잡도를 가진다. 일반적으로 많은 경우에 사용되는 balanced tree가 height <= log(N+1)을 보장하기 때문에 비추어진 결과이다.
Balanced Tree는 리프노드들의 depth차이가 1이상 나지 않는 트리로, 트리 자체만으로는 효율적인 자료구조가 아니다. 이는 다음과 같이 긴 꼬리를 가진 Tree형태가 존재하기 때문이다.
따라서 트리와 Balanced Tree의 관계는 Balance Tree ⊂ Tree 이다.
그러나 해당 문제의 경우 트리의 깊이를 조정하는 Balancing 작업을 할 경우 정작 중요한 부모, 자식 관계가 수정되기 때문에 공통 조상이 무엇인지 찾을 수 없게 될 수 있다.
따라서 트리 자체를 재편하기 보다. 동적 계획법을 사용하여 부모 배열을 2 ** i 번째의 부모 배열을 담도록 개편하여 노드를 올라가는 과정을 축약하면 더욱 수월하게 풀 수 있을 것이다.
성능을 개선하기 위해선 배열을 2차원 배열로 만들고, 각 배열의 요소에 2**i 번째 부모를 저장해야 한다.
예를 들어 위와 같은 트리의 부모 정보를 저장한다면 parent 배열은 다음과 같을 것이다.
이를 Recursive하게 저장한다면 다음과 같이 저장할 수도 있을 것이다.
이렇게 구현하면 최대 O(N*log(N))만큼의 공간복잡도가 필요하다.
이진수를 활용하자. 컴퓨터 공학을 배운 사람이라면 알다시피 모든 수는 이진수를 통해 변환될 수 있다.
특히 2. 두 노드를 찾아 동일한 Depth로 맞추기 부분에서 두 노드의 depth 차이 만큼 올라와야 하는 부분에서 이진수를 적용한다면 다음과 같이 노드를 올라오도록 할 수 있을 것이다.
두 노드의 depth 차가 11일 경우: 8 + 2 + 1과 같은 형식으로 수를 만들어 올라오게 지정할 수 있을 것이다.
또한 3. 하나씩 노드를 올라가며 공통된 조상을 찾기 부분 역시 개선할 수 있다. 이미 위 부분에서 두 노드의 depth가 같도록 설정되었을 것이므로, 생성된 배열을 역으로 탐색해가며 내려오다가, 해당 부모의 노드가 서로 달라질때를 기준으로 부모 노드를 적절히 변경하면, 2**i 번씩 부모를 변경하면서 공통 조상노드를 찾을 수 있다.
parent = [[0] * LOG for _ in range(N + 1)]
def set_parent():
dfs(1, 0)
for i in range(1, LOG):
for j in range(1, N + 1):
parent[j][i] = parent[parent[j][i - 1]][i - 1]def lca(node_1, node_2):
# 노드의 깊이는 1번이 더 작게 설정
if depth[node_1] > depth[node_2]:
node_1, node_2 = node_2, node_1
# 두 노드의 depth 맞추기
for i in range(LOG - 1, -1, -1):
if depth[node_2] - depth[node_1] >= 2 ** i:
node_2 = parent[node_2][i]
if node_1 == node_2:
return node_1
for i in range(LOG - 1, -1, -1):
if parent[node_1][i] != parent[node_2][i]:
node_1 = parent[node_1][i]
node_2 = parent[node_2][i]
return parent[node_1][0]import sys
from pprint import pprint
def dfs(node: int, d: int):
# 깊이 설정 (현재노드)
depth[node] = d
visited[node] = True
# 자식 노드의 부모 설정
for adj_node in graph[node]:
if not visited[adj_node]:
parent[adj_node][0] = node
dfs(adj_node, d + 1)
def set_parent():
dfs(1, 0)
for i in range(1, LOG):
for j in range(1, N + 1):
parent[j][i] = parent[parent[j][i - 1]][i - 1]
def lca(node_1, node_2):
# 노드의 깊이는 1번이 더 작게 설정
if depth[node_1] > depth[node_2]:
node_1, node_2 = node_2, node_1
# 두 노드의 depth 맞추기
for i in range(LOG - 1, -1, -1):
if depth[node_2] - depth[node_1] >= 2 ** i:
node_2 = parent[node_2][i]
if node_1 == node_2:
return node_1
for i in range(LOG - 1, -1, -1):
if parent[node_1][i] != parent[node_2][i]:
node_1 = parent[node_1][i]
node_2 = parent[node_2][i]
return parent[node_1][0]
LOG = 21
N = int(sys.stdin.readline())
depth = [0] * (N + 1)
parent = [[0] * LOG for _ in range(N + 1)]
visited = [False] * (N + 1)
graph = [[] for _ in range(N + 1)]
for _ in range(N - 1):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
set_parent()
M = int(sys.stdin.readline())
for _ in range(M):
a, b = map(int, sys.stdin.readline().split())
print(lca(a, b))
https://bbbyung2.tistory.com/76