[백준] 3584 : 가장 가까운 공통 조상 / python

1. 문제 설명

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

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

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

 

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

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

입력

그리고 그 다음 N-1개의 줄에 트리를 구성하는 간선 정보가 주어집니다.
한 간선 당 한 줄에 두 개의 숫자 A B 가 순서대로 주어지는데,
이는 A가 B의 부모라는 뜻입니다.
(당연히 정점이 N개인 트리는 항상 N-1개의 간선으로 이루어집니다!)
A와 B는 1 이상 N 이하의 정수로 이름 붙여집니다.
테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.

출력

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

 

2. 풀이 전 계획과 생각

입력

• T → 테스트 케이스의 갯수
• N → 트리를 구성하는 노드의 수 (2 ≤ N ≤ 10000)
• A, B → A가 B의 부모
  ⇒ tree 구성한다.
• 가장 가까운 공통 조상을 구할 두 노드 → vertex_A, vertex_B

구하고자 하는 바

두 노드의 가장 가까운 공통 조상

패턴

1. 트리 만든다.
   A가 B의 부모다.
   B → A로 가야하므로, tree[B].append(A)하면 된다.
2. 가장 가까운 공통 조상을 구한다.
   DFS를 통해 vertexA의 부모들을 다 찾는다. (vertexA에서 Root까지의 vertex들이다.)
   DFS를 통해 vertexB의 부모들을 다 찾는다. (vertexB에서 Root까지의 vertex들이다.)
   vertexA와 vertexB의 부모들을 교집합을 구한다.
   (그런데, vertexA와 vertexB도 서로의 부모가 될 수 있으므로, 자기자신을 추가해준다.)
   변환된 list의 가장 첫번째 값을 리턴한다.

 

3. 풀이

def make_tree():
    for vertex in range(1, N + 1):
        tree[vertex] = []

    for _ in range(N - 1):
        A, B = tuple(map(int, input().split()))
        tree[B].append(A)

def find_parent(vertex):
    if vertex == root_node:
        return
    parent.append(tree[vertex][0])
    find_parent(tree[vertex][0])

def find_near_common_parent(A, B):
    global parent
    find_parent(A)
    A_parent = parent
    parent = []
    find_parent(B)
    B_parent = parent

    find_common_parent = list(set([A] + A_parent) & set([B] + B_parent))
    return find_common_parent[-1]

for _ in range(int(input())):
    N = int(input())
    tree = {}
    parent = []

    make_tree()
    for key, value in tree.items():
        if len(value) == 0:
            root_node = key
            break
    vertex_A, vertex_B = tuple(map(int, input().split()))
    print(find_near_common_parent(vertex_A, vertex_B))

 

문제점

set으로 바꾸면 순서가 뒤바뀐다.

⇒ 순서를 바꾸지 않고 리스트의 교집합을 구하기 위해, list comprehension을 사용하자.

a = [1, 2, 3, 4, 5]
b = [9, 8, 7, 6, 5]

result = [x for x in a if x in b]

 

4. 2차 풀이

import sys
sys.setrecursionlimit(10000)

def make_tree():
    for vertex in range(1, N + 1):
        tree[vertex] = []

    for _ in range(N - 1):
        A, B = tuple(map(int, input().split()))
        tree[B].append(A)

def find_parent(vertex):
    if vertex == root_node:
        return
    parent.append(tree[vertex][0])
    find_parent(tree[vertex][0])

def find_near_common_parent(A, B):
    global parent
    find_parent(A)
    A_parent = parent
    parent = []
    find_parent(B)
    B_parent = parent
    find_common_parent = [element for element in [A] + A_parent  if element in [B] + B_parent]

    return find_common_parent[0]

for _ in range(int(input())):
    N = int(input())
    tree = {}
    parent = []

    make_tree()
    for key, value in tree.items():
        if len(value) == 0:
            root_node = key
            break
    vertex_A, vertex_B = tuple(map(int, input().split()))
    print(find_near_common_parent(vertex_A, vertex_B))

 

5. 다른 풀이

• A를 자기자신을 포함하여 루트까지 탐색하여 체크한다.
• B는 자기자신을 시작하여 루트로 이동하면서 체크된 부분과 만나는 정점을 찾는다. 출력한다.

def solve():
    n = int(input())
    par = [0] * (n + 1)
    for _ in range(n - 1):
        u, v = map(int, input().split())
        par[v] = u

    check = [0] * (n + 1)
    x, y = map(int, input().split())

    while x:
        check[x] = 1
        x = par[x]
    
    
    while y and check[y] == 0:
        y = par[y]
    print(y)

T = int(input())
for _ in range(T):
    solve()

 

6. 풀이 후 알게된 개념과 소감

• 순서를 바꾸지 않고 리스트의 교집합을 구할 때,
  a = [1, 2, 3, 4, 5]
  b = [9, 8, 7, 6, 5]
  result = [x for x in a if x in b]
• DFS 탐색할 때, visited를 활용해보자.