[백준11725&파이썬] BFS와 DFS에서 그래프 인접리스트의 활용

# 문제

백준 11725 트리의 부모찾기 파이썬 풀이

11725번: 트리의 부모 찾기

# 코드

import sys
from collections import deque
from collections import defaultdict

N = int(sys.stdin.readline().strip())

ddict = defaultdict(list)
result = [-1] * (N+1)

for i in range(N-1) :
  a,b = map(int,sys.stdin.readline().strip().split())
  ddict[a].append(b)
  ddict[b].append(a)

dq = deque()
dq.append(1)
result[1] = 1

while len(dq) != 0 :
  cur = dq.popleft()

  for next in ddict[cur] :
    # print(f"cur : {cur} , next : {next}")
    if result[next] == -1 :
      result[next] = cur
      dq.append(next)


for i in range(2,N+1) :
  print(result[i])

# 풀이

• BFS와 DFS풀이 모두 가능할걸로 보인다. DFS공부하려고 했는데 아무리봐도  BFS푸는게 쉬워보여서 BFS로 풀었다.
• 무방향으로 각 노드를 연결하고 인접리스트로 표현한다.
• 트리의 루트는 1이기 때문에, 1의 인접리스트로 BFS를 돌린다.
• 루트노드( 1 )의 인접리스트가 뽑히면, 뽑힌 노드의 부모를 루트노드로하고 방문표시 후 큐에 넣고 반복한다.