백준3584 - 가장 가까운 공통 조상 (DFS) Python

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

해당 문제는 테스트케이스마다 트리를 이루는 n개의 정점과 이를 이루는 간선, 그리고 정점 두 개의 번호가 주어질 때, 해당 두 정점의 최소 조상을 구하는 문제다.

 

문제 해결 방식

먼저 주어진 테스트케이스에 따라 tree를 구현한 뒤, 특정 노드에서부터 부모 노드를 찾아 기록한 뒤 기록한 내용은 뒤집어 반환하는 DFS 알고리즘을 구현했다. 이는 최정상 노드부터 자기 자신 노드에까지 도달하기 위해 거쳐온 노드들을 포함한 기록이기도 하다.

문제에서 요구하는 두 노드를 해당 알고리즘을 거치게 한 뒤 얻은 거쳐온 노드들의 기록 배열을 활용하여 비교하는 방식으로 문제를 해결했다.

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()

def solution (data) :
  data.pop(0)
  
  # 테스트케이스 분리
  testCase = []
  for i, v in enumerate(data) :
    if v.isdigit() : testCase.append(data[i:i+int(v)+1])
    
  result = list(map(lambda x : act(x), testCase))
  print('\n'.join(map(str, result)))

def act(case) :
  n = int(case.pop(0))
  arr = [list(map(int, v.split())) for v in case]
  a,b = arr.pop()
  
  # 트리 구현 (역방향 이동이므로 자식 노드에 부모 노드 추가)
  trees = [[] for _ in range(n+1)]
  for s,e in arr :
    trees[e].append(s)

  aList = DFS(trees, a)
  bList = DFS(trees, b)
  minLength = len(aList) if len(bList) > len(aList) else len(bList)
  
  # 이동 경로 비교
  minRoot = aList[0]
  for i in range(minLength) :
    if aList[i] == bList[i] : minRoot = aList[i]
    else : break
    
  return minRoot

def DFS(trees, node) :
  order = [node]
  orderIdx = 0
  
  while orderIdx < len(order) :
    node = order[orderIdx]    
    if not trees[node] : break
    order.append(trees[node][0])
    orderIdx += 1
    
  return list(reversed(order))
    
solution(input_data)