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

백준 11725 문제 바로가기

풀이 코드

import sys

sys.setrecursionlimit(10 ** 6)
n = int(sys.stdin.readline())  # 노드의 개수

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


for _ in range(n - 1):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)


def dfs(start):
    for i in graph[start]:
        if visited[i] == 0:
            visited[i] = start  # 방문한 노드에는 부모 노드의 번호를 적어놓는다
            dfs(i)


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

DFS를 적용하면 부모노드에서 자식 노드로 간다는 점을 생각해보면 될 거 같다! 2번노드부터 차례대로 부모노드를 출력시키는 문제인데, 이전에 풀었던 dfs문제에서는 visited를 통해 방문한 노드인지 판별했었다
이번 문제에서는 방문했다면 visited에 부모 노드의 번호를 대입하는 식으로 문제를 풀었다.

예를 들면, 첫 시작은 1번부터 탐색하기 때문에 graph[1]은 6,4가 있는데 이들의 부모 노드 번호는 전부 1번으로 for문 안에서 값을 넣어주면 된다.

회고

dfs는 부모 노드에서 자식 노드로 탐색하는 점 ! 어떻게 보면 기본적인것 같지만 기계적으로 문제를 풀다보니 까먹을수도 있다는 사실 ㅎ