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

💡 **Check Point !

( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가? ✓

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

---

난이도 체감

1. 최상

2. 상✓

3. 중✓

4. 하

---

이해도

1. 완벽히 이해✓

2. 다소 헷갈리는 부분들이 있음

3. 이해 못함

문제

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

나의 풀이

import sys
from collections import defaultdict, deque

def BFS(graph,i,visited):
    queue=deque()
    parent=[[] for _ in range(len(visited))]
    visited[i]=True
    queue.append(i)
    while queue:
        v=queue.popleft()
        for g in graph[v]:
            if not visited[g]:
                visited[g]=True
                queue.append(g)
                parent[g].append(v)
    return parent
N=int(input())

graph=defaultdict(list)
visited=[False]*(N+1)
for _ in range(N-1):
    n1,n2=map(int,sys.stdin.readline().strip().split())
    graph[n1].append(n2)
    graph[n2].append(n1)
answer=BFS(graph,1,visited)
for i in range(2,len(answer)):
    print(answer[i][0])

• BFS를 사용하여 문제를 풀었다. 원래는 BFS함수 자체에서 print를 하려고 했는데, node 2번부터 순서대로 출력해야 했기 때문에, parent리스트 안에 parent node를 따로 저장하여 프린트하였다.