백준 - 트리의 부모 찾기 (DFS, BFS) / Silver 2 / 11725번

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

11725번: 트리의 부모 찾기

 

풀이

import sys
from collections import defaultdict
from collections import deque

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

tree = defaultdict(list)

for _ in range(n - 1):
    edge = sys.stdin.readline().split()
    tree[edge[0]].append(edge[1])
    tree[edge[1]].append(edge[0])

queue = deque('1')
visited = [0] * n
visited[0] = 1
result = {str(i + 1): 0 for i in range(n)}

while queue:
    now = queue.popleft()
    for i in tree[now]:
        if visited[int(i) - 1] == 0:
            result[i] = now
            visited[int(i) - 1] = 1
            queue.append(i)

for key in result.keys():
    if key != '1':
        print(result[key])

처음 봤을 땐 되게 쉬운 문제라고 생각했는데

풀이에 실패하여 다른 사람의 풀이를 조금 참고하여 다시 한번 풀어보았다.

 

먼저 tree라는 dictionary를 만들어 node들의 연결관계를 정의하였다.

또한 result dictionary는 각 node들의 부모 node를 저장해주었다.

그 후 1번 node부터 BFS로 탐색해서 "now" node과 연결된 node들을 처음 방문한다면 

현재 node를 "now" node의 부모 node로 저장시켰다. 그리고 자식 node들을 queue에 추가해주었다.