풀이방법
이 문제는 내부 공기와 외부 공기를 구분하는 것이 가장 중요하다!!
- 처음 2차원 배열을 입력받을 때, 배열의 값이 1(치즈)인 모든 좌표를 set()에 저장한다.
- 남은 치즈가 없을 때까지 루프를 돌며 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구한다.
- 매 루프마다 현재 상태에서의 외부 공기를 새롭게 탐색한다.
external_air()함수 안에서 BFS 수행- 좌표 (0, 0) 부터 탐색을 시작하여 인접한 모든 공기를 외부 공기로 취급한다.
external_air()함수는 외부 공기인 좌표에는 True, 아닌 좌표에는 False로 초기화한 2차원 배열을 반환한다.
- 남아 있는 모든 치즈를 탐색한다.
- 남아있는 치즈의 좌/우/위/아래만 탐색하며 인접한 외부의 공기가 몇 개인지 카운트한다.
- 만약 카운트가 2 이상이면 제거 대상으로 추가한다.
- 존재하는 모든 치즈를 탐색한 후, 제거 대상이 된 치즈를 일괄 제거한다.
- 매 루프마다 현재 상태에서의 외부 공기를 새롭게 탐색한다.
정답 코드
# DFS - 2638번 - 치즈
## 내부 공기와 외부 공기를 구분하는 것이 포인트!!
import sys
from collections import deque
input = sys.stdin.readline
dy = [0, 0, -1, 1]
dx = [-1, 1, 0, 0]
r, c = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(r)]
cheese = {(y, x) for y in range(r) for x in range(c) if arr[y][x] == 1}
def external_air():
global r, c
external_arr = [[False] * c for _ in range(r)]
q = deque([(0, 0)])
external_arr[0][0] = True
while q:
y, x = q.popleft()
for k in range(4):
ny = y + dy[k]
nx = x + dx[k]
if (0 <= ny < r) and (0 <= nx < c) and arr[ny][nx] == 0 and not external_arr[ny][nx]:
external_arr[ny][nx] = True
q.append((ny, nx))
return external_arr
ans = 0
while cheese:
remove = []
ans += 1
external = external_air()
for (y, x) in list(cheese):
cnt = 0
for k in range(4):
ny = y + dy[k]
nx = x + dx[k]
if (0 <= ny < r) and (0 <= nx < c):
if external[ny][nx]:
cnt += 1
if cnt >= 2:
remove.append((y, x))
for (ry, rx) in remove:
cheese.discard((ry, rx))
arr[ry][rx] = 0
print(ans)
⚽️ 트러블 슈팅
- 메모리 초과가 발생한 이유 : 처음에 DFS를 사용할 줄 알고
sys.setrecursionlimit(10**9)로 설정을 해놨는데 여기서 메모리 초과가 발생함. sys.setrecursionlimit(n): 재귀 함수가 최대 n단계 깊이까지 호출되는 것을 허용함. 재귀 호출의 깊이 설정.- 깊이 = 함수가 자기 자신을 초훌하면서 중첩되는 호출 단계의 수
Q. 재귀 함수를 직접 호출하지 않았고, 가능하다는 설정만 했는데 왜 메모리 초과가 발생할까?
A. n이 지나치게 큰 값으로 설정되면, 파이썬 인터프리터는 예상 호출 스택을 위한 메모리를 비효율적으로 할당하려 한다. 이 과정에서 메모리 초과가 발생할 수 있다.
