[백준/Python] 3584번 가장 가까운 공통 조상

LCA(Lowest Common Ancestor)알고리즘이란?

가장 낮은 공통 조상은 n1과 n2를 모두 자손 으로 갖는 트리의 가장 낮은 노드를 말하는데, 다음 그림을 보면 노드4, 5의 공통 조상은 노드 2이고, 노드5, 6의 공통 조상은 노드1이다.

이미지 및 설명 출처 : https://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/

문제

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다.

• 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.

예를 들어  15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.

루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

입력

첫 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스마다, 첫째 줄에 트리를 구성하는 노드의 수 N이 주어집니다. (2 ≤ N ≤ 10,000)

그리고 그 다음 N-1개의 줄에 트리를 구성하는 간선 정보가 주어집니다. 한 간선 당 한 줄에 두 개의 숫자 A B 가 순서대로 주어지는데, 이는 A가 B의 부모라는 뜻입니다. (당연히 정점이 N개인 트리는 항상 N-1개의 간선으로 이루어집니다!) A와 B는 1 이상 N 이하의 정수로 이름 붙여집니다.

테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.

출력

각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력합니다.

예제 입력

2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5

예제 출력

4
3

1차 시도

이 풀이는 런타임 에러 (ValueError)가 발생한다. GPT한테 물어봤다.

주어진 코드를 살펴보면, nearest_common_anscestor 함수에서 a, b = node 코드에서 node가 2차원 리스트인데 이를 언패킹하려고 하고 있습니다.

언패킹(Unpacking)이란 리스트나 튜플과 같은 iterable한 자료형을 변수 여러 개에 나누어 저장하는 것을 의미합니다. 예를 들어, nodes = [1, 2]와 같이 리스트가 주어졌을 때, a, b = nodes와 같이 작성하면 a에는 1이 저장되고 b에는 2가 저장됩니다. 이것이 언패킹입니다.

그러나 위 코드에서 nodes는 테스트 케이스가 1개일 때에는 단일 리스트를, 여러 개일 때에는 2차원 리스트를 받습니다. 따라서 언패킹을 할 수 없고, 단일 리스트인 경우와 2차원 리스트인 경우를 모두 고려해야 합니다. => node가 2차원 리스트일 때도 고려해야함

2차 시도

1차 시도의 문제점은 입력값을 주어지면 그 입력값을 순서대로 처리하지 않았고, 입력값을 제대로 받지 못함. 입력값으로 테스트 케이스가 주어지고 테스트케이스의 수만큼 공통조상을 찾는 로직이 돌아가야 함.

노드의 개수, 간선의 정보, 공통 조상을 찾을 두 노드가 순서대로 입력되기 때문에 반복문으로 입력을 받기로 함. 보기에도 훨씬 가독성에서 나아보인다.

그런데 TypeError: unhashable type: 'list'가 발생한다.

주어진 코드에서 TypeError: unhashable type: 'list' 오류가 발생하는 부분은 find_ancestors 함수 내부에서 while 루프를 돌면서 발생합니다. 이 오류는 딕셔너리의 키로 리스트 타입을 사용하려고 할 때 발생합니다.

구체적으로 말하면, tree 딕셔너리는 부모 노드를 키로 사용하고, 해당 부모 노드의 자식 노드들을 리스트로 가지고 있습니다. 그런데 find_ancestors 함수에서 tree 딕셔너리를 순회하면서 node를 찾으려고 할 때, node가 리스트 타입인 경우가 있어서 이런 오류가 발생하는 것입니다.

따라서 이 문제를 해결하려면 tree 딕셔너리의 구조를 바탕으로 find_ancestors 함수를 수정해야 합니다. 리스트 대신에 노드를 키로 사용하여 딕셔너리에서 노드의 부모 노드를 찾아야 합니다. 이렇게 수정하면 오류가 해결될 것입니다.

child를 key로, value를 parent로 tree에 저장한다. 그래서 tree에서 어떤 노드를 찾으면 그 노드의 부모 노드를 알 수 있게 했다. while문에서 tree[node]의 첫번째 부모노드 [0]를 선택했다.

그렇지만 이 코드를 돌려보면 2 만 출력된다. 푸는데 너무 오래 걸려서 결국 gpt의 힘을 빌렸다.

3차 시도 : 정답

결국 gpt에게 물어보았다. 일단 트리를 만드는 건 비슷하다.

트리에서 주어진 노드 2개를 가지고 공통 조상을 찾는 find_common_ancestor함수를 보면, 현재 node1의 부모 노드를 차례로 하나씩 가져와서 ancestor 집합에 추가한다. None을 반환할 때 까지 반복한다. node2가 집합에 있으면 가장 가까운 공통 조상이므로 node2를 바로 반환한다. 집합에 없으면 마찬가지로 node2의 부모 노드를 tree에서 하나씩 가져와서 집합에 추가한다.

while문으로 공통 조상을 찾는 로직을 간결하게 잘 구현한 것 같다.