[ 2638 ] [ BFS ] 치즈

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

2638번: 치즈

 

---

풀이 과정

---

1. 전체적으로 3가지 과정을 반복한다.
   
   1. 치즈가 더이상 남아있지 않은지 체크한다
   2. 외부 공기의 위치들을 따로 구해준다.
      • 이 과정에서 테두리는 무조건 외부 공기로 간주해도 되기 때문에, (0, 0)에서부터 1이 아닌 0을 만나는 경우에 대해서만 BFS를 진행해주면 된다.
   3. 각각의 치즈와 인접한 4개의 칸 중 몇개의 칸이 외부 공기인지 개수를 구하고, 2개 이상이라면 제거해 준다. 이 때, 한번에 제거해 주어야 제거로 인해 다른 치즈가 영향을 받지 않는다.
   4. 시간을 1초 증가시켜 준다.
2. 치즈가 남아있지 않는다면, 총 몇초가 지났는지 출력시켜 준다.

---

소스 코드

---

import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()

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

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

def get_air_pos():
    air = set()
    air.add((0, 0))
    queue = deque([[0, 0]])
    
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx and nx < N and 0 <= ny and ny < M:
                if (nx, ny) not in air and matrix[nx][ny] == 0:
                    air.add((nx, ny))
                    queue.append([nx, ny])

    return air

def is_empty():
    for i in range(N):
        for j in range(M):
            if matrix[i][j] != 0:
                return False
    return True

def destroy_cheese(air):
    destroy_cheese_pos = []
    for i in range(N):
        for j in range(M):
            if matrix[i][j] == 1:
                air_count = 0
                for k in range(4):
                    x, y = i + dx[k], j + dy[k]
                    if (x, y) in air:
                        air_count += 1
                if air_count >= 2:
                    destroy_cheese_pos.append([i, j])
                    
    for x, y in destroy_cheese_pos:
        matrix[x][y] = 0
                            

time = 0
while True:
    if is_empty():
        break
    air = get_air_pos()
    destroy_cheese(air)
    time += 1
    

print(time)