[BOJ] 3584 가장 가까운 공통 조상

3584 가장 가까운 공통 조상 문제 링크
문제 풀이 코드 링크

문제 요약

트리가 주어지고, 특정 노드 2개가 주어졌을 때 해당 노드의 가장 가까운 공통 조상 노드를 출력한다.

아이디어

보통 트리는 부모 노드에 자식 노드를 저장해 관리하지만, 이번엔 자식노드의 조상 노드들이 필요한 경우이기 때문에 자식 노드에 부모 노드를 저장하였다. 부모 노드는 1개이기 때문에 1차원 배열로 해결할 수 있다.

1. 주어진 2개의 노드 중 하나를 정해, 해당 노드의 조상 노드들을 list로 만들어 관리한다.
2. 나머지 한 개의 노드에 대해, 해당 노드의 부모 노드가 1의 list에 포함되는지 검사한다.
3. 포함되지 않는 경우 그 노드의 부모노드에 대해 똑같이 검사한다.

구현

import sys
input = sys.stdin.readline

T = int(input())


for _ in range(T) :
  N = int(input())
  
  parents = [-1 for i in range(N+1)]

  for i in range(N-1) :
    A, B = map(int, input().split(" "))
    parents[B] = A

  n1, n2 = map(int, input().split(" "))
  
  n1_ancestor = []
  cur = n1

  while cur != -1 :
    n1_ancestor.append(cur)
    cur = parents[cur]
    
  cur = n2
  result = -1
  while cur != -1 :
    if cur in n1_ancestor :
      result = cur
      break
    cur = parents[cur]
  
  print(result)