출처: Unsplash
📌 목차
- 설명
- 접근 방식
- 코드
📌 설명
- 노드의 개수와 트리에 연결된 두 정점이 주어졌을 때,
- 각 노드의 부모 노드 번호를 순서대로 출력해야 한다.
📌 접근 방식
- 모든 노드를 방문하면서 트리를 그려나가야 한다.
- 따라서 이 문제의 핵심은 각 노드를 방문하는 대표적인 알고리즘인 "DFS/BFS" 를 이용하는 것이다.
- 여기에 각 부모 노드의 번호를 알아야 하므로 DFS/BFS를 하면서 부모 노드에 대한 그래프를 그려 나가도록 했다.
📌 코드 (DFS)
import sys
sys.setrecursionlimit(10**6)
N = int(input())
tree = [[] for _ in range(N + 1)]
parent = [None for _ in range(N + 1)]
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(tree, 1, parent)
for i in range(2, N + 1):
print(parent[i])