[Python] 백준 20058 마법사 상어와 파이어스톰

1. 문제 - 백준 20058 마법사 상어와 파이어스톰

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

 

시뮬레이션, 빡구현 문제는 먼저 기능 별로 함수로 나누는게 중요하다.

 

* 문제에서 설명하는 파이어스톰 분석

1) 단계 L 을 입력받는다. 마지막 줄에 L1, L2, ... LQ가 Q개만큼 주어지고, Q번만큼 마법을 시전함

2) 2^N X 2^N 격자의 얼음판에서 2^L X 2^L 격자로 나누어, 각 격자의 모든 부분을 90도 회전시킨다.

3) 이후 얼음이 있는 칸 3개 또는 그 이상과 인접하지 않은 칸은 얼음의 양이 1 줄어든다.

 

여기서 반복하는 기능을 함수화하면 된다.

1. 2^L X 2^L 격자로 나누어, 각 격자의 모든 부분을 90도 회전하기, 2. 인접한 칸이 얼음이 있는 칸이 3개 이상인 얼음 찾기

 

그리고 모든 파이어스톰을 시전한 마지막에 다음 2가지를 구해야한다.

1) 남아있는 얼음 A[r][c]의 합 --> 반복문을 통해 얼음의 갯수 총합을 구하면 됨

2) 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수 --> 얼음이 남아있는 칸 기준으로 DFS/BFS 실행 (함수화)

 

✅ 풀이 과정

1) 입력받고, 인접한 칸을 구할 때 사용할 offset 배열 미리 선언하기

n, q = map(int, input().split())   # 파이어스톰 총 q번 시전
que = []    # 마법사 상어가 시전한 단계들을 담을 리스트 (L 배열)
grid = []
dx = [-1, 1, 0, 0]      # 인접한 칸을 구하기 위한 offset 배열
dy = [0, 0, -1, 1]

for _ in range(2**n):
  grid.append(list(map(int, input().split())))
que = list(map(int, input().split()))

 

2) 2^L X 2^L 크기의 부분 격자로 나누어, 각 격자를 시계 방향으로 90도 회전시키는 함수 만들기

def rotate_subgrid(grid, x, y, l):
  size = 2 ** l
  new_grid = [[0] * size for _ in range(size)]
  for i in range(size):
      for j in range(size):
          new_grid[j][size - 1 - i] = grid[x + i][y + j]
  for i in range(size):
      for j in range(size):
          grid[x + i][y + j] = new_grid[i][j]

def rotate_all(grid, l):
  n = len(grid)
  step = 2 ** l
  for i in range(0, n, step):
    for j in range(0, n, step):
        rotate_subgrid(grid, i, j, l)   # 격자 시작점에서 2^L X 2^L 크기의 격자들 90도 회전시키는 함수

 

3) 인접한 칸들 중 얼음이 있는 칸이 3개 이상인지 판단하는 함수

def judge(x, y):    # 얼음이 있는 칸 3개 혹은 그 이상과 인접해있지 않은 칸을 판단하기 위한 함수
  count = 0
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]

    if 0<=nx<2**n and 0<=ny<2**n and grid[nx][ny] > 0:
      count += 1

  if count >= 3:
    return True
  else:
    return False

 

4) 모든 파이어스톰을 시행한 다음, 얼음의 갯수를 셀 함수

def count_ice():
  count = 0
  
  for i in range(2**n):
    for j in range(2**n):
      count += grid[i][j]

  return count

 

5) 얼음이 남아있는 칸들 중 가장 영역이 큰 구역의 갯수를 세기 위한 BFS 함수

def bfs(x, y):            # 가장 큰 덩어리를 구성하는 칸의 갯수를 세기 위한 그래프탐색 (BFS) 함수
    queue = deque([(x, y)])
    visited[x][y] = True
    cnt = 1

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < 2**n and 0 <= ny < 2**n:
                if not visited[nx][ny] and grid[nx][ny] > 0:
                    visited[nx][ny] = True
                    queue.append((nx, ny))
                    cnt += 1
    return cnt

 

 

이들을 종합하여 문제의 조건에 맞게 프로그래밍하면 다음과 같다.

from collections import deque

n, q = map(int, input().split())   # 파이어스톰 총 q번 시전
que = []    # 마법사 상어가 시전한 단계
grid = []
dx = [-1, 1, 0, 0]      # 인접한 칸을 구하기 위한 offset 배열
dy = [0, 0, -1, 1]

for _ in range(2**n):
  grid.append(list(map(int, input().split())))
que = list(map(int, input().split()))

def rotate_subgrid(grid, x, y, l):
  size = 2 ** l
  new_grid = [[0] * size for _ in range(size)]
  for i in range(size):
      for j in range(size):
          new_grid[j][size - 1 - i] = grid[x + i][y + j]
  for i in range(size):
      for j in range(size):
          grid[x + i][y + j] = new_grid[i][j]

def rotate_all(grid, l):    # 2^L X 2^L 격자에서 시계 방향 90도 회전하기 위한 함수
  n = len(grid)
  step = 2 ** l
  for i in range(0, n, step):
    for j in range(0, n, step):
        rotate_subgrid(grid, i, j, l)

def judge(x, y):    # 얼음이 있는 칸 3개 혹은 그 이상과 인접해있지 않은 칸을 판단하기 위한 함수
  count = 0
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]

    if 0<=nx<2**n and 0<=ny<2**n and grid[nx][ny] > 0:
      count += 1

  if count >= 3:
    return True
  else:
    return False

visited = [[False] * 2**n for _ in range(2**n)]
def bfs(x, y):            # 가장 큰 덩어리를 구성하는 칸의 갯수를 세기 위한 그래프탐색 (BFS) 함수
    queue = deque([(x, y)])
    visited[x][y] = True
    cnt = 1

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < 2**n and 0 <= ny < 2**n:
                if not visited[nx][ny] and grid[nx][ny] > 0:
                    visited[nx][ny] = True
                    queue.append((nx, ny))
                    cnt += 1
    return cnt

def count_ice():             # 모든 파이어스톰을 실행한 다음 얼음의 갯수를 셀 함수 
  count = 0
  
  for i in range(2**n):
    for j in range(2**n):
      count += grid[i][j]

  return count

for l in que:         # 각 파이어스톰 시전 L들을 담은 배열마다 L순회
  rotate_all(grid, l)   # 격자 회전
  to_reduce_ice = []

  for i in range(2**n):
    for j in range(2**n):
      if grid[i][j] > 0 and not judge(i, j):    # 인접한 얼음이 있는 칸의 갯수가 3개 이상일 경우, 녹여야하므로 좌표 저장
        to_reduce_ice.append((i, j))   # 녹여야할 얼음들 좌표 추가하기

  for x, y in to_reduce_ice:    # 녹여야하는 얼음 좌표들 대상으로 얼음 녹이기
    grid[x][y] -= 1
  
answer1 = count_ice()
print(answer1)

answer2 = 0
for i in range(2**n):
  for j in range(2**n):
    if grid[i][j] > 0 and not visited[i][j]:
      answer2 = max(answer2, bfs(i, j))   # 얼음칸들이 있는 구역의 갯수 중 최대값 갱신하기
print(answer2)

 

❓ 구역의 넓이 최대값을 구할 때 사용하는 그래프탐색 함수를 BFS가 아닌 DFS로 했을 때, 메모리 초과가 발생하는 이유

처음에 RecursionError가 뜨길래 recursionlimit을 늘렸지만, 그럼에도 메모리 초과가 발생했다.

GPT한테 물어본 결과 다음과 같다.

 

1. 최대 그리드 크기 파악

2 ≤ N ≤ 6 → 그리드 크기: 2^N × 2^N → 최대 64 × 64 = 4,096칸

👉 4천 개 칸이면 작다고 생각될 수 있지만, 덩어리 탐색을 DFS로 할 경우 한 번에 4천 번 재귀 호출이 발생할 수도 있어요.

📌 일반적으로 Python에서는 재귀 깊이 1,000~2,000 이상은 위험합니다.
→ PyPy는 안전하지만 Python3은 Stack Overflow 또는 MemoryError 가능성이 있어요.

---

2. Q (시전 횟수)가 많다 → visited나 DFS 반복 횟수가 많아진다

1 ≤ Q ≤ 1,000

• Q번 회전하고 그 후 얼음 감소 연산, 그 후 한 번만 dfs() 탐색하므로 dfs()는 한 번뿐임
• 하지만 덩어리가 클 경우, 그 1번의 DFS가 수천 번의 재귀로 이어질 수 있음

---

3. 결정 포인트: 덩어리 탐색 시 단일 DFS 깊이가 얼마나 클까?

• 입력 조건만 보면, grid 내 얼음이 0인 칸도 많을 수 있지만
• 만약 "거의 모든 칸이 얼음"인 테스트케이스가 들어오면?
  → 전체 4,096칸이 하나의 연결된 덩어리
  → dfs() 깊이: 최대 4,096

📌 이건 DFS 재귀 깊이 한계(Python에서는 안전한 범위가 아님)

 

즉, 최대 4096번의 재귀가 발생할 수 있기 때문에 Recursion Error 혹은 Memory Error가 발생할 가능성이 있다고 한다.

따라서 재귀로 DFS를 구성할 경우, 재귀의 깊이가 어느정도가 최대값인지 보고 미리 예측할 필요가 있어보인다.