[백준 2468번] 런타임 에러(RecursionError), Boolean Table 과 메모리.

이 문서는 전문적이지 않습니다.

입력 : 첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

출력 : 첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

배열속에 있는 다양한 배열을 여러 조건에서 탐색해야한다.

 

 

 

 

#1

 

 

 

 

뭔가.. 뭔가 작동할 것 같았다..

 

 

그림으로 그리면서 필요할것 같은 함수를 적어가며 코드를 쓰기 전에 간략하게 스케치했다.

이렇게 하니 어느부분을 수정하고 보완해야 더 나아질까 한 눈에 보여서 좋았다.

 

 

import sys


def fromL(i, j, h, listK): # 왼쪽에서 탐색을 접근한 경우
    if i >=0 and i < T and j >= 0 and j < T and (i,j) not in listK: # i 와 j 가 0보다 크거나 같고 TestCase 값보다 작아야 한다. (0 ~ T-1의 범위 안에 있어야한다.)
        if listHeight[i][j] > h: # 해당하는 값이 잠긴 높이보다 클 경우
            listK.append((i,j)) # 해당 좌표 (i,j)를 리스트에 저장한다.
            
            if (i-1,j) not in listK:
                fromB(i-1,j,h,listK)
            
            if (i, j+1) not in listK:
                fromL(i,j+1,h,listK)

            if (i+1, j) not in listK:
                fromT(i+1, j, h, listK)

    return listK


def fromR(i, j, h, listK): # 오른쪽에서 탐색을 접근한 경우
    if i >=0 and i < T and j >= 0 and j < T:
        if listHeight[i][j] > h:
            listK.append((i,j))

            if (i-1,j) not in listK:
                fromB(i-1,j,h,listK)

            if (i, j-1) not in listK:
                fromR(i,j-1,h,listK)

            if (i+1, j) not in listK:
                fromT(i+1, j, h, listK)

    return listK


def fromT(i, j, h, listK): # 위쪽에서 탐색을 접근한 경우
    if i >=0 and i < T and j >= 0 and j < T:
        if listHeight[i][j] > h:
            listK.append((i,j))

            if (i, j-1) not in listK:
                fromR(i,j-1,h,listK)

            if (i, j+1) not in listK:
                fromL(i,j+1,h,listK)

            if (i+1, j) not in listK:
                fromT(i+1, j, h, listK)

    return listK


def fromB(i, j, h, listK): # 아래쪽에서 탐색을 접근한 경우
    if i >=0 and i < T and j >= 0 and j < T:
        if listHeight[i][j] > h:
            listK.append((i,j))

            if (i, j-1) not in listK:
                fromR(i,j-1,h,listK)

            if (i, j+1) not in listK:
                fromL(i,j+1,h,listK)

            if (i-1,j) not in listK:
                fromB(i-1,j,h,listK)

    return listK

T = int(sys.stdin.readline().rstrip()) # Test case

listHeight = [None] * T # 높이의 행 렬 메모리


listH = [] # 높이의 종류 메모리

for i in range(T) :
    listHeight[i] = list(map(int, sys.stdin.readline().rstrip().split(' ')))
    for j in listHeight[i]:
        if j not in listH:
            listH.append(j)

for h in listH: # 각 높이별로 구분
    if h != max(listH): # 만약 최대높이가 아니라면

        maxCnt = 0
        listY=[]
        for i in range(T): # i 는 행이다
            for j in range(T): # j 는 열이다
                listK = []
                key = False
                if listY:
                    for x in range(len(listY)):
                        if (i,j) in listY[x]:
                            key = True
                if not key:
                    fromL(i,j,h,listK)
                if listK not in listY and listK:
                    listY.append(listK)
        if maxCnt < len(listY):
            maxCnt = len(listY)

print(maxCnt)

 

 

이후 작성된 코드다. 해당 코드에서는 어디서 접근했는지로 4개의 함수를 만들었다.

거짓말처럼 maxCnt 가 정상적으로 출력됐고, 너무 두근거렸다.

 

 

제발.. .. ..

 

 

 

 

처음보는 에러. RecusionError

 

 

 

RecursionError는 재귀와 관련된 에러입니다. 가장 많이 발생하는 이유는 Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어질 때입니다.
Python이 정한 최대 재귀 깊이는 sys.getrecursionlimit()을 이용해 확인할 수 있습니다. BOJ의 채점 서버에서 이 값은 1,000으로 되어 있습니다.

출처 : https://help.acmicpc.net/judge/rte/RecursionError

런타임 에러 (RecursionError)

 

 

 

 

 

 

 

#2

 

 

 

 

 

재귀 깊이때문에 생기는 오류였다. 이를 해결하기 위해서 수동으로 최대 재귀 깊이를 변경하였다.

sys.setrecursionlimit(10**5)

 

 

또한 위에 선언한 "오른쪽" "왼쪽" "위" "아래" 로 나누어진 함수를 하나로 통합시켰다.

 

import sys

sys.setrecursionlimit(10**5)

def fromA(i, j, h, listK:list): # 왼쪽에서 탐색을 접근한 경우
    if i >=0 and i < T and j >= 0 and j < T and (i,j) not in listK: # i 와 j 가 0보다 크거나 같고 TestCase 값보다 작아야 한다. (0 ~ T-1의 범위 안에 있어야한다.)
        if listHeight[i][j] > h: # 해당하는 값이 잠긴 높이보다 클 경우
            listK.append((i,j)) # 해당 좌표 (i,j)를 리스트에 저장한다.
            
            fromA(i-1,j,h,listK)
            
            fromA(i,j+1,h,listK)

            fromA(i+1, j, h, listK)

            fromA(i,j-1,h,listK)

    return listK

T = int(sys.stdin.readline().rstrip()) # Test case

listHeight = [False] * T # 높이의 행 렬 메모리


listH = [False] * 100 # 높이 도수분포

for i in range(T) :
    listHeight[i] = list(map(int, sys.stdin.readline().rstrip().split(' ')))
    for j in listHeight[i]:
        if not listH[j]:
            listH[j] = True


maxCnt = 0
for h in range(len(listH)): # 각 높이별로 구분
    if listH[h]:

        listY = []
        for i in range(T): # i 는 행이다
            for j in range(T): # j 는 열이다
                listK = []
                key = False
                if listY:
                    for x in range(len(listY)):
                        if (i,j) in listY[x]:
                            key = True
                if not key:
                    fromA(i,j,h,listK)
                if listK:
                    listY.append(listK)

        
        if maxCnt < len(listY):
            maxCnt = len(listY)
print(maxCnt)

 

 

진짜 많이 줄였다.. 고 생각하며 부푼 마음을 가졌다.

 

 

 

 

 

 

 

 

PyPy3 는 메모리 초과, Python3는 시간초과

 

 

 

#3

 

그래도 열심히 했다.. 정답자와 나의 차이는 무엇이었을까?

 

참고자료 : https://velog.io/@phw1996/%EB%B0%B1%EC%A4%80-2468%EB%B2%88-%EC%95%88%EC%A0%84-%EC%98%81%EC%97%AD-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[Python] 백준 2468번 '안전 영역' 풀이

 

가장 접근방법이 비슷하다고 느낀 풀이방법이다.

해당 풀이와 내 풀이의 가장 큰 차이점은 방문한 기록에 대한 저장이었다.

내 코드에서는 방문 기록을 튜플형태로 함수 내부에서 append 시켜줬고,

정답자의 코드에서는 Boolean Table 형태로 방문기록을 변경했다.

 

 

 

 

 

 

글을 마치며

 

 

 

확실히 코드도 짧아지고 불필요한 반복문이 줄었다. 또한, 이전에도 공부한듯이 반복문에서 append 시키는 작업이 효율적인 메모리 활용의 관점에서  "나쁜 코드" 임을 아는 나에게는 오늘도 하나를 배울 수 있었다. 사실 다른 문제에서도 Boolean Table을 사용했으나, 이번 TIL을 통해 조금더 나에게 익숙하게 만들자.

 

앞으로 잘 하자.

 

 

 

 

긴 글 읽어주셔서 감사드립니다.

22.11.02