BOJ(백준) 11725[트리의 부모 찾기]

안녕하세요! 이번 글에서는 백준 11725번 문제인 “트리의 부모 찾기” 문제를 함께 해결해 보겠습니다. 이 문제는 트리 구조에서 각 노드의 부모를 찾는 문제입니다. 문제를 분석하고, 접근 방법을 정리한 후, 최종적인 정답 코드를 확인해 보겠습니다.

 

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

 

1. 문제 설명

1) 문제 개요

트리 구조에서 각 노드의 부모를 찾는 문제입니다. 주어진 트리는 N개의 노드를 가지고 있으며, 각 노드는 1번부터 N번까지의 번호를 갖습니다. 1번 노드는 항상 루트 노드입니다. 우리는 각 노드의 부모를 출력해야 합니다.

 

2) 입력

• 첫 번째 줄: 노드의 수 N (2 ≤ N ≤ 100,000)

• 다음 N-1개의 줄: 두 노드 사이의 간선을 나타내는 두 정수 a, b

 

3) 출력

• 각 노드 2번부터 N번까지의 부모 노드를 출력합니다.

 

2. 접근법

1) 입력받기

• 빠른 입력을 위해 sys.stdin.readline을 사용합니다.

• 트리를 인접 리스트로 표현하여, 노드 간의 연결을 저장합니다.

 

2) DFS를 이용한 부모 찾기

• DFS(깊이 우선 탐색)를 이용해 각 노드의 부모를 찾습니다. 루트 노드인 1번 노드에서 시작하여, 연결된 노드를 탐색하면서 부모 노드를 기록합니다.

• 방문하지 않은 노드를 찾을 때마다, 해당 노드의 부모를 현재 노드로 설정하고, 다시 DFS를 수행합니다.

 

3) 결과 출력

• 각 노드의 부모를 2번 노드부터 N번 노드까지 출력합니다.

3. 정답 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)        # 재귀 호출 한도를 설정하여 깊은 재귀를 지원

# 입력
N = int(input())  # 노드의 개수
adj = [[] for _ in range(N+1)]      # 인접 리스트 초기화 (1부터 N까지 사용)

# 간선 입력 받아 인접 리스트에 저장
for _ in range(N-1):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

# 부모 노드를 저장할 배열 초기화
# 0번 인덱스는 사용하지 않고, parent[1]은 루트 노드이므로 0을 넣음
# 나머지는 아직 부모가 설정되지 않았음을 나타내기 위해 -1로 초기화
parent = [0] + [0] + [-1] * (N-1)

# DFS를 통해 각 노드의 부모 노드를 찾는 함수
def dfs(idx):
    for i in adj[idx]:          # 현재 노드와 연결된 노드들을 탐색
        if parent[i] == -1:     # 부모 노드가 아직 설정되지 않은 경우
            parent[i] = idx     # 현재 노드를 부모로 설정
            dfs(i)              # 연결된 노드에 대해 DFS 수행

dfs(1)  # 1번 노드가 루트이므로 DFS 시작

# 각 노드의 부모 노드 출력 (2번 노드부터 N번 노드까지)
for i in range(2, N+1):
    print(parent[i])

 

4. 코드 설명

1) 입력 받기

• sys.stdin.readline을 사용하여 노드의 수 N과 간선 정보를 빠르게 입력받습니다.

• 인접 리스트 adj를 사용하여 각 노드에 연결된 다른 노드들을 저장합니다.

 

2) DFS를 이용한 부모 찾기

• parent 리스트를 초기화하여 각 노드의 부모를 저장할 수 있도록 합니다. 루트 노드인 1번 노드는 부모가 없으므로 0으로 설정합니다.

• DFS 함수는 재귀적으로 호출되며, 현재 노드와 연결된 노드들 중 부모가 설정되지 않은 노드를 찾아 그 노드의 부모를 현재 노드로 설정합니다.

 

3) 결과 출력

• DFS가 완료된 후, 각 노드의 부모를 2번 노드부터 N번 노드까지 출력합니다.

 

5. Github으로 확인

coTest/BOJ/BOJ01_09_03_11725.py at main · pcy4196/coTest