[파이썬/python] 백준 11725 - 트리의 부모 찾기

문제

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

---

문제 설명

1. 루트 없는 트리가 주어진다.
2. 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구해라.

---

단순 DFS를 사용하여 각 노드의 부모를 구하는 문제이다.

풀이

1. 루트 노드가 1번이므로 1번 노드부터 DFS탐색을 시작한다. 
2. 현재 방문한 노드를 이전 노드의 값(부모 노드)으로 방문 처리한다.
3. 2번 노드부터 순차적으로 부모를 출력한다.

---

코드

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

n = int(input())
graph = [[] for _ in range(n+1)]
visited = [0 for _ in range(n+1)]

for i in range(n-1):
    v1,v2 = map(int,input().split())
    graph[v1].append(v2)
    graph[v2].append(v1)

def dfs(v1):
    for v2 in graph[v1]:
        if not visited[v2]:
            visited[v2] = v1
            dfs(v2)

dfs(1)

for v in visited[2:]:
    print(v)

---

시간복잡도

• 인접 리스트를 통한 DFS의 시간복잡도는 $O(V+E)$이다.
• 노드의 개수는 최대 $10^5$ 간선의 개수는 최대 $10^5-1$
• 따라서 최악의 경우 시간복잡도는 약$O(2*10^5-1)$이다.