📃 문제 설명

트리의 부모 찾기

[문제 출처 : 백준]

👨‍💻 해결 방법

노드의 부모를 저장할 리스트 answer를 만든다.
(answer[2]의 값은 2번 노드의 부모)

그 후 주어진 stack을 이용하여 입력대로 저장되어 있는 graph를 깊이 우선 탐색하며
각 노드의 부모를 구한다.

처음에 문제를 이해하는데 시간이 조금 걸렸지만,
dfs를 이용하여 쉽게 풀 수 있었다.

재밌다

👨‍💻 소스 코드

N = int(input())

graph = {}
for _ in range(N - 1):
    a, b = map(int, input().split())
    if a in graph:
        if b not in graph[a]:
            graph[a].append(b)
    else:
        graph[a] = [b]

    if b in graph:
        if a not in graph[b]:
            graph[b].append(a)
    else:
        graph[b] = [a]

answer = [0] * (N + 1)
stack = [1]

while stack:
    n = stack.pop()
    if answer[n]:
        continue
    if n in graph:
        if n == 1:
            answer[n] = -1
        else:
            for v in graph[n]:
                if answer[v]:
                    answer[n] = v
        temp = sorted(graph[n], reverse=True)
        stack.extend(temp)

print(*answer[2:], sep='\n')