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

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

3584번: 가장 가까운 공통 조상

문제

루트가 있는 트리(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 이하의 정수로 이름 붙여집니다.

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

 

출력

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

---

Recursive(재귀)로 노드1의 조상들을 Set에 등록하고, 다시 노드2의 조상들을 탐색하며 Set에 등록되어있는지 여부를 확인하여 공통된 조상을 찾아내었다.

 

- 노드 n의 부모를 저장하는 parents[n] 배열을 만들어주었다. 

- 최대 노드의 갯수가 10,000으로, sys.setrecursionlimit(10**4+1) 을 해주어야 런타임 에러가 발생하지 않는다.

import sys

sys.setrecursionlimit(10**4+1)

def findParent(node, parentSet):
    global res

    # 최상위 node에 도달하였거나, 공통된 조상을 찾은 경우
    if node == 0 or res != -1:
        return

    if node in parentSet:
        res = node
        return

    parentSet.add(node)
    findParent(parents[node], parentSet)

### MAIN
tc = int(sys.stdin.readline().strip())
for _ in range(tc):

    n = int(sys.stdin.readline().strip())
    parents = [0 for _ in range(n + 1)]
    for _ in range(n-1):
        parent, child = map(int, sys.stdin.readline().split())
        parents[child] = parent

    # print(parents)
    node1, node2 = map(int, sys.stdin.readline().split())
    parentSet = set()
    res = -1

    findParent(node1, parentSet)
    findParent(node2, parentSet)

    print(res)