[백준] 11725번 트리의 부모 찾기 (Python) - RecursionError 발생

문제와 입출력 조건

예제 입출력

 

시간 복잡도와 공간 복잡도(런타임 에러 RecursionError)

시간 제한과 메모리 제한

BFS, DFS의 시간 복잡도는 O(V+E)이다. 노드의 개수는 최대 100000개이고 간선의 개수는 99999개이기에 O(199999)가 최악의 시간 복잡도이다. Python3는 1초에 2000만번 연산이 가능하기에 O(199999)가 문제가 되지 않아 보이지만, Python3 기준 최대 재귀 깊이는 1000이기에 199999번 재귀호출 할 경우 RecursionError가 발생한다. 그래서 재귀 호출을 이용하는 DFS보다는 반복문 베이스인 BFS를 이용해서 이 문제를 해결해야 한다.

---

자연어 알고리즘과 코드

1. 입력을 받고 조건대로 Graph와 방문 테이블을 생성한다.

2. bfs 함수를 정의한다.

3. bfs 함수 내부에 부모 노드를 기록하는 parent 리스트를 생성한다.

    각 인덱스는 n 번째 노드를 뜻하고, 그 인덱스가 가르키는 메모리 공간에 위치한 값은 부모 노드이다.

4. bfs 함수 내부에서 탐색을 완료하면 parent 리스트를 반환한다.

5. 탐색 시작 노드를 1번으로 설정하여 bfs 함수를 호출한다.

6. parent 리스트를 인덱스 2부터 끝까지 출력한다.

 

import sys
from collections import deque

input = sys.stdin.readline 
n = int(input())
graph = [ [] for i in range(n+1)]
visitied = [False] * (n+1)

def bfs(graph,node, visited):
    queue = deque([node])
    visited[node] = True
    parent = [None] * (n+1)

    while queue:
        cur = queue.popleft()
        for i in graph[cur]:
            if not visited[i]:
                parent[i] = cur
                queue.append(i)
                visited[i] = True
    return parent


for i in range(n-1):
    x,y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

parent = bfs(graph, 1, visitied)
[print(i) for i in parent[2:]]

---

소감(배운 점)

1. 시간 복잡도가 커질 때, DFS 재귀 함수 호출에 한계가 있으므로 BFS를 먼저 고려해보자.

2. 입력이 많을 때는 sys.stdin.readline 을 사용하여 입력 시간을 줄이자.