[백준] 11725번 트리의 부모 찾기 - Python / 알고리즘 기초 2/2 - 트리 1

---

---

---

💡 문제

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

입력

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

출력

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

---

💭 접근

기본적인 그래프 탐색 문제로, 입력받은 트리에 대해 DFS / BFS를 사용하여 각 노드의 부모 노드를 저장하면 되는 간단한 문제이다.

---

📒 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def dfs(start):
    for next in graph[start]:
        if parent[next] == 0:
            parent[next] = start
            dfs(next)

n = int(input())
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
parent = [0 for _ in range(n + 1)]
parent[1] = 1

dfs(1)

print(*parent[2:], sep='\n')

---

💭 후기

오랜만에 쉬운 문제라 가벼운 마음으로 풀었던 문제였다!

---

🔗 문제 출처

https://www.acmicpc.net/problem/11725

---