[백준/Python] 3584번(DFS, 그래프 이론)_가장 가까운 공통 조상

📌문제 유형

 DFS, 그래프 이론 (골드 Lv.4)

 

📌문제

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

 

📌나의 문제풀이

- maps에 B(자식)에 [A(부모)] 저장

- DFS에서 상위 부모들 route에 모두 저장

• route들의 순서 유지한 교집합 구하기

- 해당 방법으로 풀 경우, recursionlimit에 걸리므로 setrecursionlimit을 늘려야 함

# 그래프 이론으로 풀면 recursionlimit 안 늘려도 될 듯
import sys
sys.setrecursionlimit(10**5)

t = int(input())

def dfs(x, route):
    if maps[x] != []:
        route.append(maps[x])
        dfs(maps[x], route)
    return route

for _ in range(t):
    n = int(input())

    # B(자식)에 [A(부모)] 저장
    maps = [[] for _ in range(n+1)]
    for _ in range(n-1):
        a,b = map(int,input().split())
        maps[b] = a
    # 가까운 공통조상 구할 노드
    result_1, result_2 = map(int,input().split())
    route1, route2 = [result_1], [result_2]
    ans1 = dfs(result_1, route1)
    ans2 = dfs(result_2, route2)

    # 기존 순서 유지한 교집합 구하기
    result = [x for x in ans1 if x in ans2]
    print(result[0])

 

📌 다른사람의 문제풀이

- LCA

[백준] 3584번 - 가장 가까운 공통 조상 (파이썬)

# 가장 가까운 공통 조상

def find_parent(parent, x):
    result = [x]
    while parent[x]:
        result.append(parent[x])
        x = parent[x]
    return result


T = int(input())
for _ in range(T):
    N = int(input())
    parent = [0 for _ in range(N+1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        parent[b] = a

    x, y = map(int, input().split())
    # 각 부모 리스트 정의
    x_parent = find_parent(parent, x)
    y_parent = find_parent(parent, y)

    # 깊이 맞춰주기
    i, j = 0, 0
    if len(x_parent) > len(y_parent):
        i = len(x_parent) - len(y_parent)
    else:
        j = len(y_parent) - len(x_parent)

    # 같은 깊이에서 최소 공통 조상 찾기
    while x_parent[i] != y_parent[j]:
        i += 1
        j += 1
    print(x_parent[i])

 

📌 리뷰

- 관점을 반대로 바라보기(보통은 부모노드에 자식 저장, 이번 경우는 자식 노드에 부모 저장)

- 순서 유지 교집합

순서유지 교집합 - python list ordered intersection