2022.05.09 [백준] (python 파이썬) 가장 가까운 공통 조상

 

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

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

---

풀이

이 문제는 주어진 노드에서 부모 노드를 확인하며 공통 부모 노드를 찾는 문제이기 때문에 graph[자식노드]에 부모노드를 저장했다.

그리고 set배열에 먼저 주어진 노드 중 하나에 대한 부모 노드를 모두 저장해 주었다. 여기서 set을 사용한 이유는 set안의 존재여부를 판단할 때, 시간 복잡도가 O(1)이 걸리기 때문이다.

하나의 노드에 대한 부모노드를 모두 저장한 후, 나머지 노드에 대해 부모의 노드를 하나씩 set에 존재여부를 판단하고 존재하면 해당 노드를 출력 후 break로 해당 트리에 대한 조사를 멈추었다.

for _ in range(int(input())):
    N=int(input())
    graph=[[]for _ in range(N+1)]
 
    for _ in range(N-1):
        a,b=map(int,input().split())
        graph[b].append(a)
 
    a_node,b_node=map(int,input().split())
    setB = {b_node}
    while graph[b_node]:
        if graph[b_node]:
            b_node=graph[b_node][0]
            setB.add(b_node)
    while True:
        if a_node in setB:
            print(a_node)
            break
        if graph[a_node]:
            a_node=graph[a_node][0]