[baekjoon] 백준 2638번 : 치즈 (by python 파이썬) bfs

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

2638번: 치즈

 

정답 code

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

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

# bfs로 외부 공기를 탐색하며 외부공기와 접촉시마다 +1 카운트해줌
def bfs():
    queue = deque()
    #맨 가장자리에는 치즈가 안놓이는 외부공기
    queue.append([0,0])
    visited[0][0] = 1
    while queue:
        x, y = queue.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:
                #만약 외부공기와 접촉된 치즈일시 +1
                if cheeze[nx][ny] >= 1:
                    cheeze[nx][ny] += 1
                #외부공기 방문처리후 이동
                else:
                    visited[nx][ny] = 1
                    queue.append([nx,ny])


n, m = map(int,input().split())
cheeze = []


for _ in range(n):
    c = list(map(int,input().split()))
    cheeze.append(c)


time = 0  #시간 저장
while True:
    visited = [[0]*m for _ in range(n)]
    bfs()
    #삭제할 치즈 존재여부
    delete = 0
    for i in range(n):
        for j in range(m):
            #외부공기 접촉 두번이상 있을시 치즈 삭제후 // 삭제 치즈 존재 delete = 1
            if cheeze[i][j] >= 3:
                cheeze[i][j] = 0 
                delete = 1
            #외부공기와 한번만 접촉한 치즈는 녹지 않음으로 1로 복구
            elif cheeze[i][j] == 2:
                cheeze[i][j] = 1
        #삭제한 치즈가 있다면 시간 추가
    if delete == 1:
        time += 1
        #삭제할 치즈가 없다면 while문 종료  
    else:
        break

print(time)

 

solution

문제를 해결 하면서 애먹었던 점은 외부공기와 내부공기가 있는데 치즈가 외부공기에 두번이상 접촉할때만 삭제된다는 것 이였다.

이를 해결하기위해 bfs를 이용해 외부공기에서 탐색하며 만약 치즈를 만난다면 +1을 해준다.

치즈를 만난경우엔 bfs를 재귀하지 않는다.

외부 공기를 만난경우에만 방문처리하며 재귀를 해주면 외부공기 상하좌우를 탐색해 나갈 수 있다.

 

bfs를 끝내고 전체적으로 탐색하며

치즈가 있는 상태가 1이기때문에 치즈가 3이상이 된다면 공기와 두번 이상 접촉한 것인데,

이런경우에는 삭제된 치즈가 있다고 표시해주고 삭제할 치즈가 없다면 탐색을 종료한다.

삭제된 치즈가 있는경우엔 시간이 한번 경과된 것임으로 시간을 +1해준다.