[실버2] 11725번 : 트리의 부모 찾기

🛠 문제

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

👩🏻‍💻 해결 방법

그래프를 통해 트리를 만들고, 부모를 저장하기 위한 리스트를 만들었다
bfs를 사용해 트리를 방문하면서 부모의 값을 갱신해주었다
dfs보다 메모리를 적게 사용했지만, 시간은 조금 더 느렸다...(?)

소스 코드

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
parent = [0] * (n+1)
graph = [[] for _ in range(n+1)]
# 트리 생성
for _ in range(n-1):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

q = deque([1])
while q:
  now = q.popleft()

  for i in graph[now]:
    if parent[i] == 0:
      parent[i] = now
      q.append(i)

for i in range(2, n+1):
  print(parent[i])

💡 다른 사람의 풀이

재귀 최대깊이 지정을 위해 setrecursionlimit 사용

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

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

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

parent = [0] * (n + 1)
def dfs(s, graph, parent):
  for i in graph[s]:
    if parent[i] == 0:
      parent[i] = s
      dfs(i, graph, parent)

dfs(1, graph, parent)
for i in range(2, n + 1):
  print(parent[i])