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

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

11725번: 트리의 부모 찾기

 

1. 내가 작성한 코드

import sys

sys.setrecursionlimit(10**9)

n = int(input()) #노드의 개수


tree = [[] for _ in range(n+1)] #tree

parent = [0] * (n+1) #parent 저장

for i in range(n-1):
  a,b = map(int, input().split())
  tree[a].append(b)
  tree[b].append(a)

def dfs(num):
  for j in tree[num]:
    if parent[j] == 0:
      parent[j] = num
      dfs(j)

dfs(1)

for i in parent[2:]:
  print(i)

이 문제 체점 시간이 어마무시하게 걸린다 (약 8분).

 

서버가 불안정했던걸까,,

 

 

2. 해결 방법

1. 각 노드의 정보를 받은 후, 인접리스트에 삽입한다.

 

2. dfs를 돌린다. 이 때, parent가 0이라면 (아직 정보가 저장되지 않았다면) num 값(부모의 index값)을 넣어준다.

 

3. parent list의 index0,1은 필요가 없으므로 2부터 끝까지 출력해준다.

 

 

참고)

• 이 트리는 이진트리가 아니다
• dfs로 해결했다면, sys.setrecursionlimit(10**9)를 적어줘야 런타임에러가 나지 않는다.