[Python] 백준 2636: 치즈

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

2636번: 치즈

접근 로직

단순한 bfs문제라고 생각하고 접근을 하려 했으나 문제의 TC에서 알 수 있듯 바깥 공기와 맞닿은 치즈와 안쪽 구멍과 맞닿은 치즈를 구별해주는 것이 중요하다.

초반에는 녹는 치즈를 2로 따로 구별을 하고 한번에 녹여주려고 했으나... 너무 무의미한 부분이고 굳이? 싶어서 바로 녹여주는 것을 선택했다.

 

 

최종

#접근 로직: bfs로 사방탐색을 하면서... bfs를 한 번 돌 때마다 공기와 접촉한 부분은 녹았다고 처리해주기
# 치즈를 1, 공기를 0으로 할 것.
from collections import deque

dir = [(0,1),(0,-1),(-1,0),(1,0)]

def bfs():
    cnt = 0
    visited = [[False for _ in range(M)] for _ in range(N)]
    q = deque()
    q.append((0,0))
    visited[0][0] = True
    while q:
        r,c = q.popleft()

        for k in range(4):
            nr = r + dir[k][0]
            nc = c + dir[k][1]
            if 0<=nr<N and 0<=nc<M and not visited[nr][nc]: #외부 공기와 맞닿은 치즈의 경우
                if cheese[nr][nc] == 1: #치즈인 경우
                    visited[nr][nc] = True
                    cheese[nr][nc] = 0 # 녹았다!
                    cnt += 1
                else:
                    visited[nr][nc] = True
                    q.append((nr,nc))
    ans.append(cnt)
    return cnt
N,M = map(int,input().split())
cheese = [list(map(int,input().split())) for _ in range(N)]
time =0
ans =[]
while True:
    time += 1
    cnt = bfs()
    if cnt == 0:
        break
print(time-1)
print(ans[time-2])