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

리뷰

딕셔너리와 BFS를 활용하여 문제를 해결했다.

 

문제 풀이

1. KEY는 1에서 N, VALUE를 빈 리스트로 갖는 딕셔너리를 초기화 해준다.
2. 정점 A, B를 받아오고 딕셔너리의 각각의 KEY와 VALUE로 간선을 추가해 준다.
3. N + 1크기의 방문을 체크할 리스트를 0으로 초기화 해준다.
4. 루트를 1로 가정했으므로 BFS를 1을 인자로 주고 시작해준다.
5. 1을 큐에 넣어주고, 1을 방문처리 해준다. 이후 WHILE루프를 시작하여 현재 처리할 숫자의 VALUE값을 탐색하고 만약 방문하지 INDEX이라면 현재 숫자가 해당 INDEX의 부모가 된다.
6. BFS가 종료되면 방문 배열 리스트를 INDEX 2부터 차례대로 출력해 주면 된다.

 

참고 사항

출력은 2부터 N + 1까지 해줘야 한다.

 

 

정답 코드

import sys, collections


def bfs(start):
    q = collections.deque([start])
    v[start] = 1
    while q:
        index = q.popleft()
        for val in dic[index]:
            if not v[val]:
                v[val] = index
                q.append(val)


n = int(input())
dic = {i: [] for i in range(1, n + 1)}
for _ in range(n - 1):
    a, b = map(int, sys.stdin.readline().split())
    dic[b].append(a)
    dic[a].append(b)
v = [0] * (n + 1)
bfs(1)
for i in range(2, n + 1):
    print(v[i])