[BFS] 트리의 부모 노드 찾기

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

11725번: 트리의 부모 찾기

 

기존에 Union Find의 rank 개념을 활용해서 문제를 풀었고 어지간한 반례를 다 풀었었는데 틀렸습니다가 나온다..ㅠㅠ

그래서 여기저기 공부하다 인접 노드를 활용해 BFS를 이용하여 탐색으로 푼 아래 블로그 분의 포스팅을 참고하였고 공부하는 겸 구현해보았다.
https://velog.io/@dark6ro/%EB%B0%B1%EC%A4%80-11725%EB%B2%88-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EB%B6%80%EB%AA%A8-%EC%B0%BE%EA%B8%B0

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

 

코드는 아래와 같음

import sys
from collections import deque

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

graph = {node:[] for node in range(1,N+1)}
graph[1] = [1]
parents = {node:None for node in range(1,N+1)}
parents[1] = 1

for _ in range(N-1) :
    n1, n2 = map(int,sys.stdin.readline().split())
    graph[n1].append(n2)
    graph[n2].append(n1)

queue = deque()
queue.append(1)
current_parents = 1

while queue :
    current_node = queue.popleft()

    for child in graph[current_node] :
        if parents[child] == None :
            parents[child] = current_node
            queue.append(child)

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