[baekjoon] 백준 11725번(파이썬): 트리의 부모 찾기

문제

11725번: 트리의 부모 찾기

- 루트 없는 트리가 주어진다.

- 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 문제이다.

- 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다.

- N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

- 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

알고리즘

- bfs 탐색을 통해 문제를 수행한다.

- 1번 노드부터 연결된 노드를 탐색한다.

- 연결된 노드 중에 탐색하지 않은 노드를 추가하고 연결된 부모 노드를 추가한다.

코드

import sys
from collections import deque

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

# 2차원 그래프로 표현
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

# 탐색 유무
visited = [False] * (n + 1)
parent = [0] * n

# 큐에 1번 노드를 추가하여 모든 노드를 탐색
queue = deque([1])
# bfs 탐색
while queue:
    temp = queue.popleft()

    # 1번 노드와 연결된 노드중에 탐색하지 않은 노드를 추가
    for i in graph[temp]:
        if not visited[i]:
            queue.append(i)

            # 부모 노드를 추가
            parent[i - 1] = temp

            # 탐색 체크
            visited[i] = True

# 1번 노드를 제외한 나머지 노드를 순서대로 출력
for i in parent[1:]:
    print(i)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법