[백준] 3584번: 가장 가까운 공통 조상 (python)

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 이하의 정수로 이름 붙여집니다.

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

 

 

 

출력 :

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

 

 

 

 

 

 

풀이)

 

앞서 푼 콜라츠 추측과 비슷한 문제이다.

 

주어진 간선들이 입력하기 편하게 자식과 부모를 모두 알려주었으므로, 이를 이용해

 

자식 노드로부터 루트노드까지 도달하는 모든 노드를 각자의 리스트에 저장한다.

 

그 뒤 해당 노드가 같아지는 지점을 찾아 이를 정답으로 출력해주면 된다.

 

앞 인덱스부터 같은 번호를 찾게되면 O(n^2)의 시간 복잡도를 가지게 되므로,

 

거꾸로 생각해, 반대로 뒤에서부터 달라지는 지점을 찾게 되면 빠른 시간내에 해당 지점을 찾을 수 있다.

 

 

import sys
 
T = int(sys.stdin.readline())
for _ in range(T):
    n = int(sys.stdin.readline())
    # 부모 자식관계가 모두 주어지므로 1차원 배열로 진행한다.
    par = [0] * (n + 1)
 
    for i in range(n - 1):
        a, b = map(int, sys.stdin.readline().strip().split())
        # 부모자식관계
        par[b] = a
 
    x, y = map(int, sys.stdin.readline().strip().split())
 
    # 두 숫자가 처음부터 같은 조상을 가졌을 수도 있으므로, 나올 수 없는
    # 조상노드를 미리 입력해놓았다.
    par_a = [-1]
    while x:
        par_a.append(x)
        x = par[x]
 
    par_b = [-2]
    while y:
        par_b.append(y)
        y = par[y]
    
    # 뒤에서부터 달라지는 지점 찾기
    for i in range(-1, -10000, -1):
        if par_a[i] != par_b[i]:
            break
 
    print(par_a[i + 1])

 

---

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

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