[BAEKJOON]백준 11725번 트리의 부모 찾기 문제 파이썬(Python) 풀이 - 그래프(Graph), 너비 우선 탐색(BFS) 알고리즘(Algorithm), 데크(Deque) 모듈

문제

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

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

예제

입력1

7
1 6
6 3
3 5
4 1
2 4
4 7

출력1

4
6
1
3
1
4

입력2

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

출력2

1
1
2
3
3
4
4
5
5
6
6

코드

from sys import stdin
import collections


class Solution:
    def findParents(self, N: int, graph):
        queue = collections.deque()
        visited = [False] * 100001
        visited[1] = True
        parents = [0] * 100001

        # 루트 1을 뺴서 큐에 넣음
        while graph[1]:
            v = graph[1].pop(0)
            queue.append(v)

        # 큐에서 왼쪽부터 빼면서 그 값의 그래프 딸려 있는거 있나 보고 visited 체크해서 뺴면서 트리 만듬.
        while queue:
            u = queue.popleft()
            visited[u] = True
            while graph[u]:
                v = graph[u].pop(0)
                if not visited[v]:
                    parents[v] = u
                    queue.append(v)
        # 출력
        for i in range(2, N + 1):
            if parents[i] == 0:
                print(1)
            else:
                print(parents[i])


N = int(stdin.readline())
graph = collections.defaultdict(list)

# 입력 받은 값으로 그래프 양방향으로 생성
for i in range(N - 1):
    u, v = map(int, stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)
Solution().findParents(N, graph)

# 실버 2인데;;; 존나 어려움 젠장 3시간만에 품 ㅋㅋ 난 병신