[백준 11725번] 트리의 부모

백준 #11725 문제를 보여

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

백준 #11725 문제 해결

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())
graph = (() for _ in range(n+1))
level = (0)*(n+1)
visited = (False)*(n+1)
visited(0) = True

for _ in range(n-1):
  start, end = map(int, input().split())
  graph(start).append(end)
  graph(end).append(start)

def dfs(num, value):
  value += 1
  visited(num) = True
  level(num) = value
  for i in graph(num):
    if visited(i) == False:
      dfs(i, value)

dfs(1, 0)

for i in range(2, n+1):
  for j in graph(i):
    if level(j) == level(i)-1:
      print(j)
      break

• DFS(또는 BFS)를 사용하는 각 노드에 대해. 심지어저장
• 노드 2에서 노드 n으로 각 노드에 연결된 노드 중 레벨 값이 1보다 작은 노드(레벨 값이 1보다 작기 때문에 해당 노드의 부모임을 의미합니다!)
• 문제의 루트 노드가 1로 주어졌으므로 시작점은 dfs(1,0)으로 주어질 수 있습니다.
• 별도의 레벨 리스트 없이 방문으로 바로 해결 가능!