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

0.  문제 링크

 

 

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

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

---

1.  풀이 방법

 

 

일단 딕셔너리를 사용해서 B의 부모에 A를 넣었다.

이를 이용해서 각자 자신의 부모를 저장할 수 있게 만들어놓았다.

마지막에 내가 찾고자 하는 a와 b가 있다고 가정하자.

a의 부모를 루트 노드 전까지 계속해서 참조하면서 부모들을 집합에 넣었다.

마지막으로 b를 계속해서 루트 노드로 올라가면서 부모들을 집합에 있는지 확인한다.

이때 b의 어떤 부모 혹은 조부모 등등이 집합에 속한다면 그것이 가장 가까운 공통 조상이 되는 것이다.

---

2.  코드

 

 

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    T = int(input())
    par = dict()
    my_par = set()
    for _ in range(T):
        par.clear()
        my_par.clear()
        N = int(input())
        for _ in range(N - 1):
            A, B = map(int, input().split())
            par[B] = A      # B의 부모는 A임
        a, b = map(int, input().split())

        while True:
            # A의 부모를 루트 노드까지 찾음
            if a not in par:
                my_par.add(a)
                break
            my_par.add(a)
            a = par[a]

        if b in my_par:
            # 만약 거기에 b가 속해있다면 출력 후 종료
            print(b)
            continue

        while True:
            # a와 b의 공통된 조상을 찾음
            if b in my_par:
                print(b)
                break
            b = par[b]

---

3.  마무리