백준 11725 트리의 부모 찾기 python

11725번: 트리의 부모 찾기

문제

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

입력

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

출력

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

풀이

from collections import deque
n = int(input())
graph = [[] for _ in range(n + 1)]
# 노드간의 연결 그래프를 표시해줄 리스트를 만들어 줍니다/
visited = [False] * (n + 1)
# 방문처리를 해줄 리스트를 만들어 줍니다.
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited[1] = True
# n - 1 번만큼 관계를 받아주고 1번 노드를 방문처리 하여줍니다.
q = deque()
q.append(1)
while q:
    x = q.popleft()
    for i in graph[x]:
        if visited[i] == False:
            visited[i] = x
            q.append(i)
    # q라는 이름의 덱을 만들고 1을 넣어줍니다. q의 가장 앞의 값을 뽑아 연결된 
    # 노드들을 방문처리 해주고 부모 노드를 기록해 줍니다. 
    # 모든 연결된 노드를 방문할 때 까지 시행하여 줍니다.
for i in range(2, n + 1):
    print(visited[i])
    # 2번 노드부터 부모 노드를 차례로 출력하여 줍니다.