[백준] 11725번, 트리의 부모 찾기 (Python)

문제

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

11725번: 트리의 부모 찾기

 

코드

import sys
sys.setrecursionlimit(10**6)

n = int(input())
graph = [[] for _ in range(n+1)]
visited = [False for _ in range(n+1)]
parents = [0 for _ in range(n+1)]

for i in range(n-1):
    x,y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

def dfs(cur):
    visited[cur] = True
    for next in graph[cur]:
        if visited[next] == False:
            parents[next] = cur
            dfs(next)
dfs(1)
for i in range(2, n+1):
    print(parents[i])

graph에 인접리스트 형태로 입력값을 받은다음 dfs를 수행한다.

 

트리구조는 순회하지 않고 아래로만 이동하기 때문에 cur이 부모노드가 되고 next가 자식노드이다.

parents[next] 에 cur을 넣어주면된다.