[백준/BOJ] 11725 - 트리의 부모 찾기

11725 - 트리의 부모 찾기

문제

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

코드

def dfs(x, p, visited):
    global result

    stack = []
    stack.append((x, p))
    visited[x] = True

    while stack:
        v, parent = stack.pop()
        result[v] = parent

        for i in graph[v]:
            if not visited[i]:
                stack.append((i, v))
                visited[i] = True

N = int(input())
graph = [[] for _ in range(N+1)]

for i in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [False] * (N+1)
result = [0] * (N+1)

dfs(1, 0, visited)
[print(result[i]) for i in range(2, N+1)]

한마디

트리의 아래로 파고들면서 부모 노드를 함께 기록해줬다.

11725번: 트리의 부모 찾기