[BOJ/백준 11725번][PYTHON] sys 최대 깊이 설정

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

트리 문제 연습을 위해 백준 문제를 풀었다.

 

해당 문제를 읽어 보면

'''

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

'''

정말 간단한 문제가 주어지며 첫째 줄에 노드의 개수 N개가 주어지고 그 다음 N-1개의 연결된 두 정점이 주어진다.

N-1개 인 이유는 1번 노드는 루트로 고정되어있기 때문이다.

 

처음에 트리를 처음 공부하는 것이므로 어디부터 건드려야 할 지 고민이 됐다. 일단 보통의 트리 구조라면, Parent와 child가 주어질 것이지만, 지금 상황으로 보면 root를 제외하곤 어떤 연결의 관계가 주어진 것이 아닌 "그저 연결이 되었다" 이렇게 주어졌다고 판단했다. 따라서 일단 관계를 연결 시키는 것이 중요하다고 생각하여, 1차원 배열로 각 인덱스가 각 노드라 가정하고 해당 인덱스에 연결되는 값을 단순 구조로 추가하였다.

import sys

for _ in range(n-1):
    a,b = map(int, sys.stdin.readline().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)

각 배열의 행과 열 별로 의미가 추가 되었다.

이렇게 graph[a][b] 와 graph[b][a]가 둘다 채워지게 되며, 둘다 단순히 연결됨을 나타나게 되었다.

 

그렇다면 이제 찾아야 하는 것은 각 노드의 부모이다. Root를 기준으로 퍼지는 모양이기 때문에 parent는 하나이다.

따라서 생각을 하게 되었다. 어디를 기준으로 어디부터 어떤 방식으로 찾아야 할까?

 

일단 어디를 기준으로는 관계가 주어진 처음의 위치가 Root이기 때문에 Root부터 출발하기로 생각했다.

그렇다면? Root와 연결된 정점들은 graph[root]에 저장되어있다.

나는 그렇다면 graph[여기] 이 여기에 위치한 값이 parent라는 가정 하 움직이기 시작했다. 

하지만 문제가 하나 있다. (x,y) 일 때 (y,x)라는 대칭 값이 존재하게 된다. 하나는 parent의 관계이고, 하나는 child의 관계이다.

이때의 해결 방법은 visit 배열을 추가하여, 처음 접근한 것 인지에 대해서 따지는 것이다.

우리가 찾는 것은 모든 관계, 모든 부모, 이런 전체의 구조를 따지는 것이 아닌 단순히 해당 노드의 직접적인 1차 부모를 찾는 것이다.

따라서 root부터 내려가면서 첫번째 접근을 하게 되면, 무조건 graph[부모] = {자식} 관계로 접근할 수 있다.

 

각 노드의 1차적인 부모에 대한 값을 구하는 문제이기 때문에 접근 여부를 따질 visit 배열에다

첫 접근의 경우, 해당 노드의 부모의 값을 저장하게 되었다.

그리고 여기서 정해야 하는 것이 깊이 우선 탐색을 할 것인지, 너비 우선 탐색을 할 것인지 였다.

일단 첫 탐색을 공부하는 것으로서 깊이 우선 탐색의 방법으로 실행하였다.

 

visit = [0]*(n+1)

def dfs(s):
    for i in graph[s]:
        if visit[i] == 0:
            visit[i] = s
            dfs(i)

dfs(1)

이렇게 실행하였다.

dfs(1)부터 실행한 이유는, 이것이 root이며, 위에서 설명하였듯이 root부터 접근하는 것이 의미있기 때문이다.

 

이렇게 실행을 시키면

런타임 에러가 뜨게 된다. 에러를 보게 되면 RecursionError가 뜨게 된다. 뭔가 재귀에 대해서 안맞는다에 의미라고 파악된다.

파이썬이 정한 최대 재귀 깊이? 라는 말이 보인다.

 

이렇게 뜬다.

찾아본 결과, 코딩 테스트에서 자주 발생하는 런타임 에러 중 하나라고 한다. 따라서 해당 부분에 대한 제한 설정이 필요하다.

그에 대한 결과로

sys.setrecursionlimit(10**6)

이렇게 추가하게 되면 recursion의 최대 깊이가 10**6이 되며

결과는?

잘 돌아간다

 

이렇게 잘 돌아가게된다.

 

sys의 메서드에 대해서 찾아보면

이는 Python/sysmodule.c에 나타나있다.

static PyObject *
sys_setrecursionlimit(PyObject *self, PyObject *args)
{
    int new_limit;
    PyThreadState *tstate;

    if (!PyArg_ParseTuple(args, "i:setrecursionlimit", &new_limit))
        return NULL;

    if (new_limit <= 0) {
        PyErr_SetString(PyExc_ValueError,
                       "recursion limit must be positive");
        return NULL;
    }

    // 스레드 상태를 가져옴
    tstate = PyThreadState_GET();
    
    // 재귀 제한을 설정
    Py_SetRecursionLimit(new_limit);
    
    // 현재 스레드의 재귀 제한도 업데이트
    tstate->recursion_limit = new_limit;
    
    Py_RETURN_NONE;
}

// 실제 재귀 제한을 설정하는 함수
void
Py_SetRecursionLimit(int new_limit)
{
    recursion_limit = new_limit;
}

저기서 잘 보면, Py_SetRecurionsLimit(new_limit); 에 대한 부분이 있다.

재귀 제한의 체크는 Python/ceval.c 에 나타나 있다.

#define CHECK_RECURSION(tstate, where) \
    do { \
        if (tstate->recursion_depth++ > tstate->recursion_limit) { \
            tstate->recursion_depth--; \
            tstate->recursion_critical = 1; \
            Py_FatalError("Cannot recover from stack overflow."); \
        } \
    } while(0)

이 부분의 코드를 읽어보면,

tstate : 현재 python 스레드의 상태를 담고 있는 구조체 포인터

where : 매크로 호출 위치 (여기선 사용이 안된다 함)

if (tstate->recursion_depth++ > tstate->recursion_limit)

 

이 부분의 경우

recursion_depth : 현재 재귀 깊이

recursion_limit : 설정된 재귀 제한

++연산자가 후위에 있어, 비교 후 증가하게 됨.

이렇게 하게 되면, 첫 호출 시 : recursion_depth = 1이 되고, 한 번의 호출이 될때마다 1씩 증가하게 됨

여기서 if문에 해당하는 recursive_depth 가 recursive_limit보다 증가하게 되면, recursive_depth를 1개 감소시킴

그 후 recursion_critical이라는 Flag를 1로 설정하며, 1일 시 stackoverflow상황으로 인지하고 error를 발생시킴

 

이러한 코드로 recurisve 상황을 제어함을 알 수 있음