[알고리즘][Python] 백준 2638 치즈 문제 풀이

문제 출처 : www.acmicpc.net/problem/2638

2638번: 치즈

---

문제 해석 : 외부 공기에 노출된 치즈는 1시간이 지나면 모두 녹아 없어진다. 이때 모든 치즈가 녹을때 까지 얼마의 시간이 걸리는 지 구하는 문제이다. ( 4변 중 2변이상이 외부 공기에 노출 되었을 때 외부 공기에 노출된 것으로 본다.)

 

문제 풀이 : DFS를 통해서 외부 공기를 각 시간 마다 확산 시키고 이와 2변 이상 마주치는 치즈를 제거하면 문제를 풀 수 있다.

---

풀이 코드

import sys
from collections import deque

input = sys.stdin.readline

dx = [0,0,-1,1]
dy = [1,-1,0,0]

def make_air(i,j):
    visited = [[0] * M for _ in range(N)]
    Q = deque()
    Q.append([i,j])
    visited[i][j] = 1

    while Q:
        x, y = Q.popleft()

        for k in range(4):

            nx = x + dx[k]
            ny = y + dy[k]

            if 0 <= nx < N and 0 <= ny < M:
                if arr[nx][ny] != 1 and visited[nx][ny] == 0:
                    arr[nx][ny] = 2
                    Q.append([nx,ny])
                    visited[nx][ny] = 1


def check(i,j):
    x, y, = i, j
    count = 0
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]

        if 0 <= nx < N and 0 <= ny < M:
            if arr[nx][ny] == 2:
                count += 1
    if count >= 2:
        return True
    else:
        return False

def is_end():
    for i in range(N):
        for j in range(M):
            if arr[i][j] == 1:
                return False
    return True

N, M = map(int, input().split())
arr = [list(map(int,input().split())) for _ in range(N)]

make_air(0,0)

time = 0
while True:

    time += 1
    update_list = []

    for i in range(N):
        for j in range(M):
            if arr[i][j] == 1:
                if check(i,j):
                    update_list.append([i,j])

    for i,j in update_list:
        arr[i][j] = 0

    make_air(0,0)

    if is_end():
        break

print(time)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.