python 백준 2638 치즈

백준 2638 치즈

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

2638번: 치즈

 

1. 문제 

 - 외부 공기와 2개이상 맞닿은 치즈는 녹는다

 - 내부 공기와 맞닿은 치즈는 카운트하지 않는다

 - 내부 공기와 외부 공기가 이어지면 그건 외부공기로 친다

2. 접근법

 - 처음에는 외부 공기와 내부 공기를 구별을 어떻게 해줄 것인가 모든 영역을 bfs탐색을 해야하나 고민함

 - 하지만 0,0은 무조건 외부공기인데 같이 탐색되지 않으면 걔네들은 내부 공기다

 - 외부공기를 -1로 만들어주고 내부공기는 이어져있지 않으면 0으로 그대로 둔다

 - 치즈가 사라져 외부랑 내부가 이어지면 내부공기도 -1로 변환된다

 

import sys
from collections import deque
sys.stdin = open('inputs.text')

n,m = map(int,sys.stdin.readline().split())
matrix = []
visit = [[0]*m for _ in range(n)]
for _ in range(n):
    matrix.append(list(map(int,sys.stdin.readline().split())))

cheese = 0
for j in range(n):
    for i in range(m):
        if matrix[j][i] > 0:
            cheese += 1

def bfs(start):

    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    visit[start[0]][start[1]] = 1
    matrix[start[0]][start[1]] = -1
    queue = deque([start])

    while queue:
        y,x = queue.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if nx<0 or ny<0 or nx>=m or ny>=n or visit[ny][nx] == 1:
                continue
            elif matrix[ny][nx] == 0 or matrix[ny][nx] == -1:
                matrix[ny][nx] = -1
                visit[ny][nx] = 1
                queue.append([ny,nx])
            elif matrix[ny][nx] > 0:
                matrix[ny][nx] += 1


day = 0
while cheese > 0:
    cheese = 0
    bfs([0,0])
    for j in range(n):
        for i in range(m):
            visit[j][i] = 0
            if matrix[j][i] >= 3:
                matrix[j][i] = -1
            elif 0<matrix[j][i] <3:
                matrix[j][i] = 1
                cheese += 1
    day+=1
    if cheese == 0:
        break

print(day)