출처: Unsplash

[백준] 11725번: 트리의 부모 찾기

📌 목차

1. 설명
2. 접근 방식
3. 코드

📌 설명

• 노드의 개수와 트리에 연결된 두 정점이 주어졌을 때,
• 각 노드의 부모 노드 번호를 순서대로 출력해야 한다.

📌 접근 방식

• 모든 노드를 방문하면서 트리를 그려나가야 한다.
• 따라서 이 문제의 핵심은 각 노드를 방문하는 대표적인 알고리즘인 "DFS/BFS" 를 이용하는 것이다.
• 여기에 각 부모 노드의 번호를 알아야 하므로 DFS/BFS를 하면서 부모 노드에 대한 그래프를 그려 나가도록 했다.

📌 코드 (DFS)

import sys

# 자기 호출 개수 제한
sys.setrecursionlimit(10**6)

# 테스트용 파일("input.txt") 읽기
# sys.stdin = open("input.txt", "r")

# 주어진 파일을 한 줄씩 입력
# input = sys.stdin.readline

# N 입력
N = int(input())

# tree, parent 초기화
tree = [[] for _ in range(N + 1)]
parent = [None for _ in range(N + 1)]

# DFS 정의
def DFS(graph, vertex, visited):
    for i in graph[vertex]:
        # 만약 방문하지 않았을 경우 방문할 정점의 값을 할당하고 재귀함수 호출
        if not visited[i]:
            visited[i] = vertex
            DFS(graph, i, visited)

# 주어진 노드로 트리 값 할당
for _ in range(N - 1):
    node_a, node_b = map(int, input().split())
    tree[node_a].append(node_b)
    tree[node_b].append(node_a)

# DFS 함수 사용하여 parent 값 할당
DFS(tree, 1, parent)

# 각 노드의 부모 노드 번호를 2번부터 순서대로 출력
for i in range(2, N + 1):
    print(parent[i])