[BOJ] 11725. 트리의 부모 찾기 (🥈, 트리, DFS)

🔗

풀이

루트는 1이므로 1에서부터 탐색을 시작한다. 트리 구조는 사이클 형태를 갖지 않으므로 리프 노드를 찾을 때까지 DFS 방식으로 탐색해나가면 된다. parent 배열에는 각 노드들의 부모를 저장한다. 탐색 하면서 각 노드의 부모 노드의 정보를 저장하며 탐색한다. 처음에 값을 입력받을 때는 어떤 값이 부모이고 자식인지 구분되지 않기 때문에 양방향으로 입력받게 된다. 만일 탐색 도중 이미 부모 노드가 있는 노드가 있다면 그 노드는 그 노드의 부모 노드이므로 탐색하면 안 된다.

예를 들어 1 다음 2를 탐색하는 경우 둘은 양방향 연결이므로 2에도 1이 연결되어 있다. 그러나 1은 이미 루트노드이자 2의 부모 노드이므로 탐색하면 안 된다. 이 부분은 예외처리 하고 나머지 노드들만 탐색한다.

재귀

깊이가 10만까지 들어갈 수 있기 때문에 파이썬 최대 재귀 탐색 범위(999)를 넘는다. 최대 재귀 범위를 늘려줘야 한다.

import sys
input = sys.stdin.readline
from collections import defaultdict
sys.setrecursionlimit(10000000)

def dfs(p, c):
    parent[c] = p
    for i in grpah[c]:
        if parent[i] != -1:
            continue
        dfs(c, i)

grpah = defaultdict(list)
n = int(input())
for _ in range(n-1):
    a, b = map(int, input().split())
    grpah[a].append(b)
    grpah[b].append(a)

parent = [-1]*(n+1)
dfs(1, 1)
for i in range(2, n+1):
    print(parent[i])

스택

재귀로 오래걸리는 것 같아서 스택+반복문으로 바꿨는데 시간은 별 차이가 안 났다.

# 트리의 부모 찾기

import sys
input = sys.stdin.readline
from collections import defaultdict

def sol():
    stack = [1]
    while stack:
        p = stack.pop()

        for c in grpah[p]:
            if parent[c] != -1:
                continue
            parent[c] = p
            stack.append(c)

grpah = defaultdict(list)
n = int(input())
for _ in range(n-1):
    a, b = map(int, input().split())
    grpah[a].append(b)
    grpah[b].append(a)

parent = [-1]*(n+1)
parent[1] = 1
sol()

for j in range(2, n+1):
    print(parent[j])