[백준 2638] 치즈

 

문제

---

 

https://www.acmicpc.net/problem/2638

2638번: 치즈

 

나의 풀이

---

 

bfs를 사용하여 풀면 된다.

1. bfs를 (0,0)에서부터 시작한다.

2. 도중에 공기칸을 만나면 큐에 넣어주고, 치즈칸을 만나면 1을 더해준다.

3. 한 번의 bfs를 돌고나서 값이 3 이상인 칸은 2면 이상이 공기와 접하는 것이므로 이 칸의 치즈를 0으로 만든다.

4. 1~3을 모든 치즈가 녹을때까지 반복

코드

---

#https://www.acmicpc.net/problem/2638
import sys
input = sys.stdin.readline
from collections import deque

N, M = map(int, input().split())
arr = []
for _ in range(N):
    arr.append(list(map(int, input().strip().split())))
time = 0

def bfs():
    q = deque()
    q.append((0,0))
    visit = set()
    visit.add((0,0))
    while q:
        x, y = q.popleft()
        for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
            nx, ny = x + dx, y + dy
            if 0<=nx<N and 0<=ny<M and (nx,ny) not in visit:
                if arr[nx][ny] == 0:
                    q.append((nx,ny))
                    visit.add((nx,ny))
                else:
                    arr[nx][ny] += 1
    for i in range(N):
        for j in range(M):
            if arr[i][j] >= 3:
                arr[i][j] = 0
            elif arr[i][j] == 2:
                arr[i][j] = 1

while True:
    # terminate condition
    total = 0
    for i in range(N):
        total += sum(arr[i])
    if total == 0:
        print(time)
        break

    bfs()
    time += 1