🖋️ 문제
N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.
입력
첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.
출력
출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.
🤔 접근
우선 매 시간 녹아내리게 되는 지점인 'C'를 찾는 게 핵심이라고 생각했다. C를 찾기 위해서는 임의의 지점이 상하좌우로 공기랑 만나게 되는지를 확인해야 하는데, 이때 치즈가 아닌 공간에 항상 공기가 있는 것이 아니라 겉부분만 공기가 있기 때문에 처음엔 공기를 확산시키는 함수가 필요하다고 생각했다.
1. 공기를 가장자리 모든 곳에서 DFS로 확산시킨 후 시작한다. (BFS도 상관없을 것 같지만 DFS구현이 전 더 편하기 때문에...)
2. c_check함수로 'c'를 찾는다. 이때 사실 그냥 이중포문으로 전부 탐색하면서 'c'인지 아닌지 확인하는데, 여기서 시간초과를 걱정하긴 했지만 일단 구현하였다.
3. c를 찾았다면, 모든 c 지점에서 공기를 다시 확산시킨다.
4. c가 없을 때까지 2, 3번을 반복한다.
💻 내 코드
# 2638
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
table = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 바깥에서 공기를 확산시키고 닿는 면적이 2면 이상인 c를 확보
# 1. 가장자리에서 공기 확산시키기
def dfs(x, y):
# 확산처리
table[x][y] = -1
# 상하좌우로 확산
for i in range(4):
nx = dx[i] + x
ny = dy[i] + y
if 0<=nx<n and 0<=ny<m and table[nx][ny] == 0:
dfs(nx, ny)
# 초기 확산
for j in [0, m-1]:
for i in range(n):
dfs(i, j)
for i in [0, n-1]:
for j in range(1, m-1):
dfs(i, j)
# 2. c 표시
def c_check():
clist = []
for i in range(1, n-1):
for j in range(1, m-1):
if table[i][j] == 1:
count = 0
for t in range(4):
nx = dx[t] + i
ny = dy[t] + j
if table[nx][ny] == -1:
count += 1
if count >= 2:
clist.append([i, j])
table[i][j] = 'c'
return clist
count = 0
while True:
clist = c_check()
if not clist:
break
for i, j in clist:
dfs(i, j)
count += 1
# for i in range(n):
# print(table[i])
print(count)👍 제출
pypy3로도 제출해보았는데 메모리초과가 났다. 아마 pypy3는 스택오버플로가 발생한 것으로 보인다.
