트리의 부모 찾기

백준 11725번: 트리의 부모 찾기

아이디어

DFS로 루트 노드인 1번부터 탐색한다. 입력시 부모-자식 순서가 아니라는것에 주의하자.

코드

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())

visited = [False] * (N + 1)
graph = [[] for _ in range(N + 1)]
parents = [1] * (N + 1)

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


def dfs(start):
    visited[start] = True
    for i in graph[start]:
        if not visited[i]:
            parents[i] = start
            dfs(i)


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

여담

처음에 바보처럼 풀었다

def findParent(c, p, t):
    if c == t:
        print(p)
        return
    visited[c] = True
    for i in graph[c]:
        if not visited[i]:
            findParent(i, c, t)


for target in range(2, N + 1):
    findParent(1, 0, target)
    visited = [False] * (N + 1)
    visited[1] = True

노드 하나당 함수를 한 번씩 실행시켜서 계속 시간초과가 났다. 노드 하나의 부모 노드를 찾는 문제가 아니라 모든 노드의 부모 노드를 찾는 문제이기 때문에 탐색과 동시에 기록을 해 주면 된다. 앞으로 조심해야겠다.