[ baekjoon ] 트리의 부모 찾기 11725번 ( python )

문제

백준 11725 트리의 부모 찾기 풀이 ( 파이썬 )

www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

 

풀이

첫 테스트 케이스는 위의 그림인데 자신의 부모 노드를 찾는 것이다

(예를 들어 5는 3, 3은 6, 7은 4 등등)

dfs 로 들어가면서 방문하지 않았다면 현재 확인하는 노드가 부모 노드이다.

 

그리고 런타임 오류가 발생했었는데, 재귀 문제로 재귀 깊이를 늘려주면 된다고 한다.

import sys
sys.setrecursionlimit(10**9)

input=sys.stdin.readline

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


def dfs(node):
    visited[node]=True
    for i in graph[node]:
        if not visited[i]:
            answer[i]=node
            dfs(i)
    return


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

dfs(1)

for i in range(2,len(answer)):
    print(answer[i])