[백준 11437] LCA

문제

N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.

두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

입력

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.

출력

M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

---

풀이

처음 문제를 보고 생각했던 풀이는

 

1. 각 노드의 부모 정보 저장

2. 입력받은 두개의 노드(n1, n2) 중 하나 (n1) 의 모든 조상을 리스트에 저장

3. n2의 부모를 하나씩 타고 올라가며 n1의 조상에 포함돼있는지 확인

 

하지만 이 풀이는 93%에서 시간초과가 난다

 

최적화와 별개로 알고리즘의 수정이 필요해보였다

공통 조상의 조건으로 같은 depth부터 비교한다면 탐색 시간을 줄일 수 있다는 사실을 알았고 각 노드의 부모 정보를 저장하며 depth도 함께 저장하였다

N = int(input())
R = [[] for _ in range(N+1)]
visit = [False for _ in range(N+1)]
parentInfo = [0]*(N+1)
depths = [0]*(N+1)
Q = deque()

# 노드의 인접 리스트 생성
for _ in range(N-1):
    n1,n2 = map(int,input().split())
    R[n1].append(n2)
    R[n2].append(n1)

Q.append(1)
visit[1] = True
parentInfo[1] = 0 # 루트 노드의 부모를 0으로 설정
depths[1] = 0
depth = 1
while len(Q) != 0:
    cycle = len(Q)
    for idx in range(cycle):
        current = Q.popleft()
        for node in R[current]:
            if not visit[node]:
                parentInfo[node] = current  # 각 노드의 부모와 깊이 정보
                depths[node] = depth
                Q.append(node)
                visit[node] = True
    depth += 1

 

 

이후 입력받는 두개의 노드의 깊이를 맞춰주고 각 노드의 부모를 하나씩 타고 올라가며 비교하여 Lowest Common Ancestor을 탐색하였다

# 최소 공통 조상 탐색
def LCA(node1, node2):
    parent1 = node1
    parent2 = node2
    while depths[parent1] != depths[parent2]:
        if depths[parent1] >= depths[parent2]:    # 깊이 맞추기
            parent1 = parentInfo[parent1]
        else:
            parent2 = parentInfo[parent2]
    while parent1 != parent2:   # 공통 조상 찾기
        parent1 = parentInfo[parent1]
        parent2 = parentInfo[parent2]
    print(parent1)

 

수정 후에도 94%에서 시간 초과가 나길래 지인에게 코드리뷰를 부탁하였고 딕셔너리가 아닌 리스트를 사용하여 시간초과가 나는 것을 잡아내었다