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

백준 11725번

최종 제출 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

n = int(input().rstrip())
array = dict()

for i in range(1, n+1):
  array[i] = []

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

parent = [0]*(n+1)
visited = [False]*(n+1)
visited[1] = True

# 깊이 우선 탐색으로 접근하여 부모 노드 저장
def dfs(index):

  for i in array[index]:
    if visited[i] == False:
      visited[i] = True
      parent[i] = index
      dfs(i)
      visited[i] = False

dfs(1)

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

◼️ 접근 속도를 높이기 위해서 array를 리스트가 아닌 딕셔너리로 설정

◼️ sys.setrecursionlimit() 부분에서 값을 정하기가 까다로움

• 답은 맞았으나 BFS로 전환하여 문제풀이

BFS 사용

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

n = int(input().rstrip())
array = dict()

for i in range(1, n+1):
  array[i] = []

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

queue = deque()
queue.append(1)
visited = [-1]*(n+1)
visited[1] = 0

# 넓이 우선 탐색을 이용해서 부모 노드 저장
while queue:

  node = queue.popleft()

  for i in array[node]:
    if visited[i] == -1:
      visited[i] = node
      queue.append(i)


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

◼️ 밑의 결과가 DFS, 위의 결과가 BFS

• 실행시간은 DFS가 근소하게 앞서나, 메모리의 경우 BFS가 4분의 1 가량 적게 듦