[백준] 11725 트리의 부모 찾기

문제링크
https://www.acmicpc.net/problem/11725

from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

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

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

rootNode = list([] for _ in range(n+1))
visited = [False] * (n + 1)
queue = deque([1])

while queue:
  current = queue.popleft()
  visited[current] = True
  for v in graph[current]:
    if not visited[v]:
      queue.append(v)
      rootNode[v] = current
      
for r in rootNode[2:]:
  print(r)

• 접근 방법 : BFS
• 시간 복잡도 : O(N)
• 배운점
  
  밑의 제출에서는 input(), 위의 제출에서는 sys.stdin.readline()을 사용했는데, 시간이 10배 이상 차이가 났다.
  파이썬의 input() 함수는 단순 입력뿐 아니라 1️⃣개행문자를 제거하고 2️⃣prompt message를 전달받아 출력하는 기능을 포함하고 있어 sys.stdin.readline()보다 시간이 더 오래걸린다고 한다.
  그러니 여러줄의 입력을 받을 때는 반드시 input()대신 sys.stdin.readline() 을 사용하자.