https://www.acmicpc.net/problem/2638
시간 1초, 메모리 128MB
input :
-
N, M(5 <= N, M <= 100)
-
1 0 (치즈 1, 없는 부분 0 / 공백으로 구분)
output : -
치즈가 모두 녹아 없어지는데 걸리는 시간
조건 : -
4변 중에 2변 이상이 실내의 공기와 접촉 하면 녹는다.
현재의 치즈 위치를 나타내는 2차원 리스트,
1시간 후의 치즈 위치를 나타내는 2차원 리스트 필요.
치즈 기준으로 상, 하, 좌, 우에 2곳 이상이 0인지 확인. (cnt 하는 변수 필요)
모든 치즈를 확인 한 후에 시간 증가.
반복이 될때 마다 dp에 존재하는 모든 그림을 graph로 가져 와야 함.
check 함수에 들어가는 횟수를 기록해서 0번이면 모든 치즈가 지워진 것.
치즈도 내부에 있는것의 경우 녹지 않는다...
내부를 판별하려면?
치즈의 상하좌우 중 비어있는 공간을 계속 길게 체크 한다.(연구소 인지 그 선생님이 학생이 존재하는지 확인하는 문제에서 체크하는 것처럼)
상.하.좌.우 만 확인 한다면 그냥 같은 줄에 있는 다른 치즈를 내부에 있다고 생각하게 된다.
와우... BFS를 왜 쓰는 문제 였는가???
내부. 외부 판별을 BFS로 돌면서 확인 하면 된다.
치즈가 내부에 존재할 경우. 외부의 치즈에 막혀 BFS로 탐색이 불가하다.
치즈를 1로 나타내기 때문에 그 수가 3 이상으로 변경된것은 녹을 것들이다.
모눈 종이 가장자리에는 치즈가 존재하지 않는다.
이 조건으로 인해 (0, 0)에서 부터 BFS를 실행하면 된다.
녹을 때.
2변 이상이 공기와 닿는 것이기에 숫자가 3이상인 것들만 녹는다.
2인 것은 다시 1로 바꿔주자.
치즈로 바뀌는 게 없는 상황이라면 반복문을 그만 돌게 하면 될듯.
정답 코드 :
import sys
from _collections import deque
N, M = map(int, sys.stdin.readline().split())
graph = []
sec = 0
for i in range(N):
data = list(map(int, sys.stdin.readline().split()))
graph.append(data)
def BFS():
# True 이면 내부, False면 외부.
q = deque([(0, 0)])
visit = [[False] * M for i in range(N)]
visit[0][0] = True
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
while q:
node_x, node_y = q.popleft()
for i in range(4):
nx = node_x + dx[i]
ny = node_y + dy[i]
if nx >= N or nx < 0 or ny < 0 or ny >= M:
continue
if not visit[nx][ny]:
if graph[nx][ny]:
graph[nx][ny] += 1
else:
visit[nx][ny] = True
q.append((nx, ny))
def melt():
cont = False
for i in range(N):
for j in range(M):
if graph[i][j] >= 3:
graph[i][j] = 0
cont = True
elif graph[i][j] == 2:
graph[i][j] = 1
return cont
temp_cheese = []
while True:
BFS()
if melt():
sec += 1
else:
break
print(sec)
