[Baekjoon] 가장 가까운 공통 조상(python)

https://www.acmicpc.net/problem/3584

문제 접근

처음에는 DFS를 통해 자식 노드를 모두 찾으면 해당 노드 번호를 반환하도록 구현했다.

 

따라서 부모 노드의 자식을 저장하도록 트리를 만들었다.

 

하지만 결과는...

사실 노드의 갯수가 최대 10000개이기 때문에 메모리 초과가 나올 줄 몰랐다...

 

고민 끝에 최근 풀었던 Union-Find 문제를 풀었던 기억을 되살려 트리를 만들 때 부모의 자식을 저장하는 것이 아니라 자식의 부모를 저장하도록 하여 문제를 해결하였다.

 

DFS를 이용할 때는 탐색하지 않아도 될 노드를 탐색했는데 트리를 저장하는 방식을 바꾸니까 찾고자 하는 자식의 노드만 탐색하므로 시간 복잡도도 O(logN)으로 해결할 수 있었다.

 

---

풀이 과정

문제 풀이 과정을 그림으로 나타내면 다음과 같다.

 

1. 자식의 부모 저장

parents 배열의 초기값을 각 노드의 번호를 저장한다.

입력받은 노드들의 부모를 모두 저장한 후에도 parents 배열에 초기값이 저장되어 있으면 루트 노드가 된다.

# 노드의 부모는 초기값으로 자기 자신을 저장
parents = [i for i in range(N + 1)]

for i in range(N - 1):
    parent, child = list(map(int, sys.stdin.readline().split()))
    parents[child] = parent

 

2. 공통 조상을 찾고자 하는 두 노드의 부모 리스트 저장

공통 조상을 찾고자 하는 두 노드를 루트 노드에 도달할 때까지 부모 리스트를 저장한다.

child_1, child_2 = list(map(int, sys.stdin.readline().split()))
parent_1, parent_2 = [child_1], [child_2]

while parents[child_1] != child_1:
    parent_1.append(parents[child_1])
    child_1 = parents[child_1]

while parents[child_2] != child_2:
    parent_2.append(parents[child_2])
    child_2 = parents[child_2]

 

3. 저장한 부모 리스트 중 공통 조상 탐색

두 노드의 부모 리스트를 순차적으로 탐색하면서 가장 먼저 발견되는 공통 조상을 찾으면 된다.

def find_same_parent(parent_1, parent_2):
    for p1 in parent_1:
        for p2 in parent_2:
            if p1 == p2:
                return p1

---

정답 코드

"""
    백준 3584번 가장 가까운 공통 조상
"""

import sys


def find_same_parent(parent_1, parent_2):
    for p1 in parent_1:
        for p2 in parent_2:
            if p1 == p2:
                return p1


T = int(sys.stdin.readline())

for _ in range(T):
    N = int(sys.stdin.readline())

    parents = [i for i in range(N + 1)]
    target = []

    for i in range(N - 1):
        parent, child = list(map(int, sys.stdin.readline().split()))
        parents[child] = parent

    child_1, child_2 = list(map(int, sys.stdin.readline().split()))
    parent_1, parent_2 = [child_1], [child_2]

    while parents[child_1] != child_1:
        parent_1.append(parents[child_1])
        child_1 = parents[child_1]

    while parents[child_2] != child_2:
        parent_2.append(parents[child_2])
        child_2 = parents[child_2]

    print(find_same_parent(parent_1, parent_2))