[백준] 2638번: 치즈

문제

백준 - 2638번: 치즈

분석

그림 1과 같이 치즈가 외부 공기와 2면 이상 닿아있으면 1시간 뒤에 녹는다.

그러나 그림2와 같이 치즈로 둘러쌓인 공기는 내부 공기이므로 이것과 닿은 치즈들은 아무런 영향이 없다.
N * M 모눈종이에 치즈정보가 주어졌을 때 몇 시간 뒤에 치즈가 모두 사라지는지 구하는 문제이다.

이 문제에서 다음 조건을 제대로 안읽어서 오래걸렸다.

• 모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다.

이 조건으로 가장자리 중에 하나인 0, 0 에서 DFS를 진행하여 외부공기인지 판단한다. (visited배열로 방문했으면 외부 공기)

외부 공기인지 판단이 끝났으면 simulate() 로 직접 치즈에 닿은 외부 공기가 2면 이상이라면 tmp배열에 0으로 갱신해주고 마지막에 grid로 다시 옮겨준다.

while 문으로 매 반복마다 다 녹았는지 확인하고, 다 녹았을 때 hour 변수를 출력하면 해결된다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
dxs = [0,1,0,-1]
dys = [1,0,-1,0]

def in_range(x, y):
    return 0<=x<n and 0<=y<m

def dfs(x, y):
    visited[x][y] = True
    for dx, dy in zip(dxs, dys):
        nx, ny = x + dx, y + dy
        if in_range(nx, ny) and not visited[nx][ny] and grid[nx][ny] != 1:
            dfs(nx, ny)

def simulate():
    tmp = [[0]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 1:
                cnt = 0
                for di, dj in zip(dxs, dys):
                    ni, nj = i + di, j + dj
                    if in_range(ni, nj) and visited[ni][nj] and grid[ni][nj] == 0:
                        cnt += 1
                if cnt >= 2:
                    tmp[i][j] = 0
                else:
                    tmp[i][j] = 1
    for i in range(n):
        grid[i] = tmp[i][:]

def isAllMelt():
    for i in range(n):
        for j in range(m):
            if grid[i][j]:
                return False
    return True

hour = 0
while not isAllMelt():
    visited = [[False]*m for _ in range(n)]
    dfs(0, 0)
    simulate()
    hour += 1

print(hour)

끝으로..

다시 한 번 문제를 꼼꼼히 읽어야 된다는 것을 느꼈다.