백준2636(파이썬) - 치즈

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

2636번: 치즈

• 문제를 읽은 후 처음 든 생각은 BFS를 사용하자 였다.
• 이 문제의 핵심은 입력값이 0에서 1로 갔을 때만 체크를 해줘야 한다. 그래야 가장자리 부분만 녹아서 사라지기 때문이다.
• 즉, 우리가 아는 deque()를 이용한 BFS에서 방문했을 때 deque()에 좌표를 넣어주는 과정에서 if문으로 구분해줘야 할 필요가 있다고 생각했다. 따라서 0에서 0으로 갈때만 deque()에 넣도록 구현하였다.
• 0에서 1로 가면 cnt에 1을 더해서 한시간에 몇개의 치즈가 녹아 없어지는지 체크할 수 있도록 하였다.
• while문이 끝나면 한시간에 녹아없어진 치즈를 카운트 한 수를 ans라는 리스트를 만들어서 값을 넣어줬다. 그럼 순서대로 ans에 녹은치즈 cnt가 들어갈 것이고, 답을 출력할 때는 한 시간전이니까 ans[-2]값을 출력해주도록 했다.
• 그리고 cnt가 0일경우에는 더이상 치즈가 없는 것이기 때문에 while 반복문으로 bfs()함수를 한번 실행할 때마다 time변수를 1씩 증가하게 해서 만약에 bfs()함수를 실행한 값이 0 이 되면 time-1을 출력하게 했다.

import sys
from collections import deque
input = sys.stdin.readline

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

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

def bfs():
    q = deque()
    q.append([0,0])
    visited[0][0] = 1
    cnt = 0
    # 한번 while문 끝날 때마다 1시간 지난다.
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<m and visited[nx][ny]==0:
                if graph[nx][ny] == 0:
                    visited[nx][ny] = 1
                    # 치즈가 아닌 부분만 q에 넣어준다.
                    # 가장자리만 체크해주기위함
                    q.append([nx,ny])
                elif graph[nx][ny] == 1:
                    # !!!!!!!!!!!!!!!!!!!!!!!!이부분이 중요!!!!!!!!!!!!!!!!!!!!!!!!!!

                    # 가장자리 부분만 처리해주기때문에 만약에 공기와 접촉한 칸은 q에 넣어주지않는다.
                    # 넣게되면 안쪽 치즈까지 녹음 처리 되기 때문이다.
                    graph[nx][ny] = 0
                    visited[nx][ny] = 1
                    cnt += 1
    ans.append(cnt)
    return cnt

time = 0
while 1:
    time +=1
    # 특수한 경우이기 때문에 0,1 밖에 없긴하지만 visited 리스트를 하나 만들어준다.
    # 0을 1로 바꾸거나 1을 0으로 바꾸면 방문처리가 되지만, 그렇게되면 bfs특성상 다르게 구현이된다.
    visited = [[0]*m for _ in range(n)]
    cnt = bfs() 
    if cnt == 0:
        break
print(time-1)
print(ans[-2])