백준 11725 - 파이썬

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

11725번: 트리의 부모 찾기

문제 풀이

처음에는 예제 출력을 보고 어떻게 출력한거지 싶어 이해하는데 시간이 좀 걸렸다. 이 문제가 원하는 것은 각 노드의 부모 노드라는 것을 알았고, 입력된 노드들을 양방향으로 연결해 줬다. 그 후 부모 노드를 저장할 리스트와 방문 리스트를 별도로 선언한 후 탐색을 진행하였다.

 

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())

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

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

def bfs():
  q = deque()
  q.append(1)
  while q:
    v = q.popleft()
    for i in graph[v]:
      if ans[i] == 0:
        ans[i] = v
        q.append(i)


bfs()

print(graph)
print(ans)

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

여기서 중요한 점은 큐에 입력되고 나간 순서대로 출력하는 것이 아닌 각 노드의 번호를 부모 노드를 저장할 리스트이 인덱스로 사용한 것이다. 또한 2번 노드부터 출력해주기 위해 슬라이싱을 사용했다.