[알고리즘] 백준 11725 트리의 부모 찾기

문제

트리의 부모 찾기

분류

DFS

코드

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

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

parents = [0] * (N+1)  # i의 부모는 parents[i]이다

def DFS(start, tree, parents):
    for i in tree[start]:
        if parents[i] == 0:
            parents[i] = start
            DFS(i, tree, parents)

DFS(1, tree, parents)

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

해설

예전에 풀었던 문제인데도 기억이 잘나지 않아서 트리를 구현해야하나 싶었다.
우선 2차원 리스트로 연결되어 있는 것들은 다 이어준다.
그리고 DFS를 돌리는데 시작점이 분명하므로, 그 시작점에 연결된 것들은 만약 parents에 부모가 저장되어 있지 않다면 시작점의 자식이다. 그렇게 하고나면 그 시작점들은 다시 부모가 되고, 그런식으로 연결된 것들을 찾아나간다.