(Python/파이썬) - 백준(BOJ) 3584번 : 가장 가까운 공통 조상

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

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

---

• 문제 : 

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

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

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

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

 

 

 

---

• 풀이 :

트리에서의 탐색 문제였습니다.

 

아이디어는 다음과 같습니다.

 

A 에서 root로 가는 경로 ( A -> ROOT)를 저장하고. B에서 root로 가는 경로를 따라가다 A -> ROOT를 만났을 때 그 점을 출력한다.

 

풀이입니다.

 

1. 각 노드의 부모를 저장하고 있는 tree 배열을 선언하고, 문제에서 주어진 두 노드 중, A 노드에서(어떤 노드를 먼저 탐색해도 상관 없습니다.) root 노드로 가는 경로를 저장할 set을 선언합니다. (set을 사용한 이유는 경로상에 있는지 확인하기 위해 if B in set: 을 사용하는데 이 때, set의 해당 연산 시간복잡도가 O(1)이기 때문입니다. 또한 set은 중복이 허용되지 않으므로 모든 노드의 번호가 독립적이라는 보장이 있어야 합니다.)

 

2. A 에서 부모를 계속 거슬러 올라가며 경로를 parent_list에 저장합니다.

 

3. B에서 부모를 계속 거슬러 올라가며 해당 노드가 A -> ROOT의 경로인 parent_list 안에 있는지 검사하고 있다면 해당 노드를 출력하고 종료합니다. (parent_list 안에 있다는 것은 B에서 root로 가는 경로와 A에서 root로 가는 경로가 만나는 지점이라는 뜻입니다. ROOT 노드에선 두 경로가 반드시 만나므로 while문의 종료가 보장됩니다.)

 

 

 

---

• 소스코드 : 

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    N = int(input())
    tree = [0 for _ in range(N+1)]
    for _ in range(N-1):
        a,b = map(int,input().split())
        tree[b] = a
    A,B = map(int,input().split())
    parent_list = {}
    while A != 0: # A -> ROOT까지 모든 경로를 담음
        parent_list.add(A)
        A = tree[A]
    while True: # B-> ROOT까지 갈때, A -> ROOT의 경로와 만나는 부분 출력
        if B in parent_list: # A->ROOT의 경로와 만나는 부분
            print(B)
            break
        B = tree[B]