백준 11725번 바로가기

나의 풀이

# 입력
import sys
n = int(sys.stdin.readline().strip())
graph = {}
for _ in range(n-1):
  a,b = map(int, sys.stdin.readline().split())
  if a in graph:
    graph[a].append(b)
  else:
    graph[a] = [b]
  if b in graph:
    graph[b].append(a)
  else:
    graph[b] = [a]  
visitedList = [False]*n
parent = {}

# 처리
def BFS(graph, node, visitedList):
  from collections import deque
  queue = deque([node])
  visitedList[node-1] = True

  while queue:
    temp = queue.popleft()
    for i in graph[temp]:
      if not visitedList[i-1]:
        queue.append(i)
        visitedList[i-1] = True
        parent[i] = temp

BFS(graph, 1, visitedList)
for i in sorted(parent.items()):
  print(i[1])

CODE REVIEW

  1. BFS을 활용한 문제. 각 node별로 부모 node를 구하는 문제였다.
  2. 방향성이 없는 연결이라 (a,b)에 대해서 graph[a]=b graph[b]=a 모두 graph에 포함시켜야하는걸 잊지 말자.
  3. dictionary의 key를 기준으로 정렬하기 위해서는 sorted(dict.items())를 활용하면 된다. 그러면 (key,value)쌍으로 된 List를 리턴해준다.