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

-Code

import sys
sys.setrecursionlimit(10 ** 6)

def dfs(p):
    for i in tree[p]:
        if parents[i] == 0:
            parents[i] = p
            dfs(i)


n = int(input())
tree = [[] for _ in range(n + 1)]
parents = [0] * (n + 1)
for _ in range(n - 1):
    x, y = map(int, input().split())
    tree[x].append(y)
    tree[y].append(x)

dfs(1)

for i in range(2, n + 1):
    print(parents[i])

처음에는 dfs로 푸려고 일단 아래와 같이 적었습니다.

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

for _ in range(n - 1):
    x, y = map(int, input().split())
    tree[x][y] = 1
    tree[y][x] = 1


for i in range(2, n + 1):
    print(tree[i])

일단 적고 출력해보니 트리에서 1인 부분 중 하나가 부모 트리로 나오기는 하는데 어떻게 해야할지 진행이 몇일째 되지 않아서 결국 찾아보게 되었다.

찾아보니 원래 하던 대로가 아닌 해당 노드에 이어진 노드를 직접 숫자로 저장을 하고 방문 하지 않았을 경우 해당 노드에 부모 노드를 기입해주는 방법이었고 그 후에도 제한을 풀어줘야 해결이 가능했습니다.

너비 탐색이 부족해서 해당 문제를 찾아 풀려하다가 바로 막혀서 많이 아쉬웠습니다.