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

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

 

내 코드

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
visited = [0] * (N + 1)
result = [0] * (N + 1)
graph = [[] for _ in range(N + 1)]

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


def bfs(v, visited, graph):
    q = deque([v])
    visited[v] = 1
    while q:
        x = q.popleft()
        for i in graph[x]:
            if not visited[i]:
                visited[i] = 1
                result[i] = x
                q.append(i)


bfs(1, visited, graph)

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

---

Review

 

문제를 보자마자 너비우선탐색(BFS)으로 풀어야겠다고 생각 하였다.

일반적인 너비우선탐색과 코드는 똑같고,

핵심은 result[노드] = 부모 로 코드를 짜줘야한다.

result[i] = x

 

---

 

깊이 우선 탐색(DFS)으로 풀 때도 같은 방식으로 코드를 짰다.

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N = int(input())
visited = [0] * (N + 1)
result = [0] * (N + 1)
graph = [[] for _ in range(N + 1)]

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


def dfs(v, visited, graph):
    visited[v] = 1
    for i in graph[v]:
        if not visited[i]:
            visited[i] = 1
            result[i] = v
            dfs(i, visited, graph)


dfs(1, visited, graph)

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

 

재귀를 이용하여 DFS를 사용하였으니 문제에 따라 재귀의 깊이를 늘려줘야 한다.

BOJ의 채점 서버에서 이 값은 1,000으로 되어 있기 때문에

sys.setrecursionlimit()을 사용해서 늘려줘야 한다.

늘려주지 않는다면 RecursionError 가 발생한다.

sys.setrecursionlimit(10 ** 6) # 최대 재귀 깊이를 1,000,000 정도로 크게 설정