트리의 부모 찾기 - Python, BFS, 재귀 깊이 제한 키우기

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

 

 

 

코드

 

import sys
from collections import deque, defaultdict

def find_parents(N, edges):
    graph = defaultdict(list)

    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)

    parent = [0] * (N + 1)
    visited = [False] * (N + 1)

    q = deque([1])
    visited[1] = True

    while q:
        node = q.popleft()

        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                parent[neighbor] = node
                q.append(neighbor)

    return parent[2:]

# 입력 처리
if __name__ == "__main__":
    sys.setrecursionlimit(10 ** 6)
    data = sys.stdin.read().splitlines()

    N = int(data[0])
    edges = [list(map(int, line.split())) for line in data[1:]]
    results = find_parents(N, edges)
    print("\n".join(map(str, results)))

 

 

풀이

 

그래프를 그려서 BFS로 탐색을 했습니다.

 

1이 ROOT이니까

 

1부터 시작해서

 

1에 연결되어 있는 node에 방문합니다.

 

이 node들의 부모는 1이므로 이를 등록해주면서

 

큐에 넣어줍니다.

 

이를 반복하면 각 노드의 부모를 알 수 있게 됩니다.

 

방문 처리를 하면서 중복을 방지했습니다.

 

특이한 점은 입력 처리에서 재귀 호출의 깊이 제한을 증가 시킨 부분입니다.

 

파이썬의 기본 재귀 깊이 제한은 1,000으로 매우 작기 때문에,

트리 탐색과 같은 깊은 재귀 호출이 필요한 경우 sys.setrecursionlimit()을 사용해 제한을 늘려줍니다.

 

 

 

 

다음에 또 봐요