[백준] 2638번 - 치즈 (파이썬)

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

# 치즈
import sys
from collections import deque
import copy
input = sys.stdin.readline
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def air_check(arr):
    q = deque()
    q.append((0, 0))
    arr[0][0] = 2
    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] == 0:
                    arr[nx][ny] = 2
                    q.append((nx, ny))
    melt_check(arr)


def melt_check(arr):
    for x, y in cheese:
        if arr[x][y] == 1:
            air = 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:
                        air += 1
            if air >= 2:
                melt.append((x, y))
    melt_cheese()


def melt_cheese():
    while melt:
        x, y = melt.pop()
        arr[x][y] = 0


N, M = map(int, input().split())
arr = []
cheese = []
melt = []
for i in range(N):
    arr.append(list(map(int, input().split())))
    for j in range(M):
        if arr[i][j] == 1:
            cheese.append((i, j))

result = 0
while True:
    is_melt_all = True
    for x, y in cheese:
        if arr[x][y] == 1:
            is_melt_all = False
            break
    if is_melt_all:
        break
    temp = copy.deepcopy(arr)
    air_check(temp)
    result += 1

print(result)

 

BFS

1. 전체 리스트(arr)을 받으면서 1인 부분만 cheese리스트에 추가

2. cheese리스트 내부의 x, y좌표를 이용해서 arr[x][y]가 1이면 치즈가 남아 있는 상태, 치즈가 전부 녹아 없어질 때까지 반복

  - 공기체크 (arr_check) : 0,0에서 bfs를 이용해서 연결된 공기만 2로 초기화 (copy.deepcopy를 사용해서 원래 arr은 수정X)

  - 녹일 치즈 체크하기 (melt_check) : 인접한 공기가 2개 이상이면 melt리스트에 append

  - 치즈 녹이기 (melt_cheese) : melt 리스트의 x, y를 이용해서 원래 arr의 값을 0으로

  - result += 1

3. result 출력 (걸린 시간)