[백준 2636] 치즈 (python)

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

2636번: 치즈

치즈 문제

공기 중에 닿은 치즈를 1시간에 한번씩 녹여갈 때, 걸리는 시간과 녹기 1시간 전 남아있는 치즈 조각을 찾는 문제

 

# 사용 알고리즘

너비 우선 탐색

📌문제 접근 포인트

1. 외부와 닿아있는 치즈를 찾을 방법을 생각해보자. 단순게 생각했을 때 (0,0)부터 시작해서 0인 부분을 기준으로 탐색을 하고, 0과 맞닿아 있는 1만을 따로 녹여주는 방법을 생각해보자.

2. 맞닿은 치즈를 따로 모아서 한번에 녹여주고, 다시 (0,0) 부터 하나씩 탐색을 진행해보자. 이것을 모두 녹일 때 까지 반복탐색을 하도록 구성해주자.

3. 전체 치즈 갯수에서 녹인 치즈 갯수를 계속해서 차감해나가고, 0이 됐을 때 직전의 치즈와 반복한 횟수를 구해서 출력해주면 성공 

⚙ 내가 푼 정답 코드

def find():
    queue = deque([(0,0)])
    melt = []
    while queue:
        y, x = queue.popleft()
        for dy, dx in move:
            ny, nx = y + dy, x + dx
            if 0 <= ny < N and 0 <= nx < M and not visited[ny][nx]:
                visited[ny][nx] = 1
                if cheeze[ny][nx] == 0:
                    queue.append((ny,nx))
                else :
                    melt.append((ny,nx))
    for y, x in melt:
        cheeze[y][x] = 0
    return len(melt)

import sys
from collections import deque
N, M = map(int, sys.stdin.readline().split())
cheeze = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
move = [[0,1],[0,-1],[1,0],[-1,0]]
cnt = sum(sum(i) for i in cheeze)
result = 1

while True: # 반복하며 녹여보자
    visited = [[0] *M for _ in range(N)]
    now = find() 
    cnt -= now
    if cnt == 0 : # 0이 되면, now는 직전의 값
        print(result)
        print(now)
        break
    result += 1