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

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

공부 날짜 : 2023.02.08
정답 참조 여부 : X

트리 구조에서 두 노드의 공통조상을 찾는 문제이다.

---

트리라는 구조를 처음 다뤄봐서 어떤식으로 구현을 해야할지 먼저 생각했다.

각 노드의 부모 노드를 알아야하고, 자식 노드를 알아야 할거 같아서 리스트에 [부모노드, [자식노드 리스트]]의 형태로 저장했다.

나중에 1~n 인 구조가 아니라면 [부모노드, 자신의 값, [자식노드 리스트]] 이런식으로 저장하면 되지 않을까 생각 했다.

하지만 이번 문제에선 자식노드를 알 필요없이 부모노드만 알면되서 부모노드 값만 저장해 줬다.

---

문제를 푼 방법은 리스트의 인덱스에 자신의 부모노드를 저장했고, root_node는 0으로 저장해 줬다.

그리고 찾아야 하는 두개의 노드에대해서 부모 노드로 거슬러 올라가며 root_node까지 경로른 적었고

2개의 경로에서 역순으로 찾다가 서로 다른값이 나오면(경로가 달라지면) 이전의 값을 출력하는 식으로 구현했다.

---

내가 구현한 트리방법이 맞는지 정답 코드를 몇개 찾아봤는데
정답 자체는 일치 했다. 문제는 트리의 구현 방법이 맞는지 알아보고 싶었는데 같은 문제를 푼사람들은 전부 나랑 같이 부모노드만 저장해 줬고, 푸는 방법도 똑같아서 크게 도움이 되진 않았다...

그냥 트리 구현하는 방법을 찾아봐도 되겠지만, 실전에서 사용되는 코드를 보는게 중요하다고 생각하니 나중에 트리 관련 문제를 풀어보면서 구현하는 방법도 알아봐야겠다.

소스코드

import sys
input = sys.stdin.readline
###################################################
# 경로를 찾는 함수
def Find_path_node(a, root_node):
    node = a
    root_node = root_node
    path = [0, a]
    while True:
        if node == root_node:
            break

        path.append(tree[node])
        node = tree[node]

    return path


###################################################
t = int(input())
for test_case 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

    # 루트노드를 찾아줌
    for i in range(1, n+1):
        if tree[i] == 0:
            root_node = i
            break

    # 공통조상을 찾아야할 두 노드
    a, b = map(int, input().split())
    if a == b:
        print(a)
        continue

    path_a = Find_path_node(a, root_node)
    path_b = Find_path_node(b, root_node)

    index_a = len(path_a) - 1
    index_b = len(path_b) - 1

    while True:
        if path_a[index_a] != path_b[index_b]:
            break
        index_a -= 1
        index_b -= 1

    print(path_a[index_a + 1])