[Silver II] 트리의 부모 찾기 - 11725

문제 링크

성능 요약

메모리: 50276 KB, 시간: 320 ms

분류

그래프 이론, 그래프 탐색, 트리, 너비 우선 탐색, 깊이 우선 탐색

문제 설명

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

---

문제 풀이

아이디어

value에 대해서 그래프를 탐색할 때, graph[value]에 방문하지 않은 노드가 있다면 그 노드의 부모는 value이다.

bfs로 그래프를 1부터 평소처럼 순환하되, graph[value]를 돌 때, 방문하지 않은 노드 i의 부모 노드는 value 이므로, data[i]에 value 값을 넣는다.

지난번에 풀 때는 dfs로 딕셔너리로 풀었더라. 근데 나는 dfs보다는 bfs가 훨씬 기억에 잘 남아서 이번에는 bfs를 사용한듯 하다.

처음에 시간초과가 발생하였는데, 처음에는 bfs(v)로 하여, for문을 2부터 n+1까지 돌리면서 매번 bfs가 실행되게 해서 그런거 같다. 사실 순환 한번 하면 바로 값이 나오는건데 생각을 잘 못 했다.

코드

import sys
from collections import deque


def bfs():
  queue = deque()
  queue.append(1)
  visited[1] = True
  while queue:
    value = queue.popleft()
    for i in graph[value]:
      # i가 방문되지 않았으면, i의 부모는 value이다.
      if not visited[i]:
        data[i] = value
        queue.append(i)
        visited[i] = True


# n 입력 받기
n = int(sys.stdin.readline().rstrip())

# graph에 정보 입력 받기
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
  a, b = map(int, sys.stdin.readline().rstrip().split())
  graph[a].append(b)
  graph[b].append(a)

# data 리스트에는 자신의 부모 값이 들어간다. 초기화
data = [0] * (n + 1)
# 방문 했는지 여부 확인하는 visited 리스트
visited = [False] * (n + 1)

# bfs 함수 실행
bfs()

# 2부터 n까지 정답 출력
for i in range(2, n + 1):
  print(data[i])