[Python] 치즈 (백준 2636번 파이썬)

 

백준 2636번 - 치즈

 

문제 바로가기

2636번: 치즈

 

 

🙄 문제 이해

 

치즈가 공기 중에 노출되면 한 시간 뒤 녹게 됩니다.

사각형의 판 안에서 치즈가 전부 사라지는 과정에서 전부 녹는데 걸리는 시간과 마지막에 남는 치즈의 갯수를 구하는 문제입니다.

 

 

📝 문제 풀이

 

BFS로 해결했고, 마지막 결과를 구하는 로직에서 어려움을 겪었습니다.

 

문제를 풀면서 했던 생각은 아래와 같습니다.

가장자리 부분을 -1로 바꿔야함(벽 만들기)

빈칸을 탐색하는데

다음 탐색 칸이
- 빈칸(0)이면 -> 방문처리하고 큐에 넣음
- 치즈(1)이면 -> 방문처리하고 빈칸으로 바꿈. *큐에 넣지는 x
- 벽(-1)은 처리 x


치즈가 모두 녹는데 걸리는 시간 + 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수?
-> 이걸 어떻게 구할 것인가?

BFS함수 종료하기 전에 지울 치즈의 갯수를 체크(리턴)

while문으로 BFS함수 반복 실행.
실행시마다 전체 치즈 - 지울 치즈 갯수

if 치즈 다 지워지면 종료

시간 +1

 

 

 

💻 Python 코드

#백준 2636 치즈
from collections import deque
import sys
input = sys.stdin.readline

def bfs():
    visited = [[False]*m for _ in range(n)]
    visited[0][0] = True
    q = deque()
    q.append((0,0))
    rm = []

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

        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                visited[nx][ny] = True
                if graph[nx][ny] == 0:
                    q.append((nx, ny))
                elif graph[nx][ny] == 1:
                    rm.append((nx,ny))
    for x,y in rm:
        graph[x][y] = 0
    return len(rm)

n, m = map(int, input().split())
graph = []
count = 0
for i in range(n):
    arr = list(map(int, input().split()))
    graph.append(arr)
    count += sum(graph[i])

time = 1
while True:
    melt = bfs()
    count -= melt
    if count == 0:
        break
    time += 1

print(time)
print(melt)