[파이썬/백준 20058] 마법사 상어와 파이어스톰/런타임에러(RecursionError) 원인과 해결방법

www.acmicpc.net/problem/20058

20058번: 마법사 상어와 파이어스톰

1. 입력

n, q = map(int, input().split())
n = 2**n
ice_rink = [list(map(int, input().split())) for _ in range(n)]
level = list(map(int, input().split()))

 

2. 구현

 

(1) 가장 큰 얼음 덩어리가 차지하는 칸의 개수

import sys
sys.setrecursionlimit(10 ** 5)

seen = set()
ice = sum(sum(ice) for ice in ice_rink)
def area(r, c):
    if not (0<=r<n and 0<=c<n and (r, c) not in seen and ice_rink[r][c]):
        return 0
    seen.add((r,c))
    return (1 + area(r+1, c) + area(r-1, c) + area(r, c-1) + area(r, c+1))

파이어 스톰이 끝난 후의 빙판에서 얼음 덩어리를 탐색하고, 그 중 가장 큰 얼음 덩어리의 크기를 리턴해주는 코드다.

파이썬은 재귀호출을 1000번으로 제한하고 있기 때문에, 그 이상으로 재귀호출을 사용하려면 sys 라이브러리에서 setrecursionlimit(n)모듈을 사용해서 제한할 횟수를 설정해주어야한다. 

 

안그러면

런타임 에러(Recursion Error)가 발생할 수 있다. 

 

(2) q번의 파이어스톰 후 빙판의 상태

direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for l in level:
    rotate = [[0] * (n) for _ in range(n)]
    k = 2 ** l
    for i in range(0, n, k):
        for j in range(0, n, k):
            for i2 in range(k):
                for j2 in range(k):
                    rotate[i + j2][j + k - i2 - 1] = ice_rink[i + i2][j + j2]

    ice_rink = [[0] * (n) for _ in range(n)]
    for r in range(n):
        for c in range(n):
            adj = 0
            for dr, dc in direction:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and rotate[nr][nc] != 0:
                    adj += 1
            if rotate[r][c] > 0:
                if adj < 3:
                    ice_rink[r][c] = rotate[r][c] - 1
                else:
                    ice_rink[r][c] = rotate[r][c]

빙판을 회전하고 인접한 얼음의 개수가 3개 미만인 경우에는 얼음을 녹여줬다.

회전을 할 때 사용한 식은 아래에서 아이디어를 얻었다.

 

0, 0	0, 1	0, 2
1, 0	1, 1	1, 2
2, 0	2, 1	2, 2

행렬 1

 

예를들어 위와 같은 이차원 행렬이 있을때, 이를 90도 회전하면 

 

2, 0	1, 0	0, 0
2, 1	1, 1	0, 1
2, 2	1, 2	0, 2

행렬2

 

이렇게 되는데, 숫자의 모양을 보면 행렬1[i, j] -> 행렬2[N-1-j][i]라는 규칙을 찾을 수 있다.

 

3. 전체 코드 

import sys
sys.setrecursionlimit(10 ** 5)

n, q = map(int, input().split())
n = 2**n
ice_rink = [list(map(int, input().split())) for _ in range(n)]
level = list(map(int, input().split()))
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for l in level:
    rotate = [[0] * (n) for _ in range(n)]
    k = 2 ** l
    for i in range(0, n, k):
        for j in range(0, n, k):
            for i2 in range(k):
                for j2 in range(k):
                    rotate[i + j2][j + k - i2 - 1] = ice_rink[i + i2][j + j2]

    ice_rink = [[0] * (n) for _ in range(n)]
    for r in range(n):
        for c in range(n):
            adj = 0
            for dr, dc in direction:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and rotate[nr][nc] != 0:
                    adj += 1
            if rotate[r][c] > 0:
                if adj < 3:
                    ice_rink[r][c] = rotate[r][c] - 1
                else:
                    ice_rink[r][c] = rotate[r][c]

seen = set()
ice = sum(sum(ice) for ice in ice_rink)
def area(r, c):
    if not (0<=r<n and 0<=c<n and (r, c) not in seen and ice_rink[r][c]):
        return 0
    seen.add((r,c))
    return (1 + area(r+1, c) + area(r-1, c) + area(r, c-1) + area(r, c+1))

biggest = max(area(r, c) for r in range(n) for c in range(n))

print(ice, biggest, sep='\n')