백준 2636. 치즈 (Python)

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

풀이

공기와 접촉된 치즈는 매 턴마다 녹아 공기가 되는 문제이다.
이때, 중요한 점은 치즈로 둘러쌓인 공기 주변의 치즈는 녹지 않는다.
즉, 치즈를 녹일 수 있는 공기와 녹일 수 없는 공기를 별도로 분리하는게 핵심!

• 처음, 치즈를 녹일 수 있는 공기를 분리한다(배열에서 0->2로 변경)
• 그리고 본격적인 턴에 들어간다.
  - bfs를 이용해 치즈를 녹일 수 있는 공기 주변 1칸에 있는 치즈들을 별도로 배열에 넣는다.
  • 만약, 치즈를 녹일 수 있는 공기 주변에 치즈를 녹일 수 없는 공기가 있다면, 해당 공기를 0->2로 바꿔준다
  • 이후, 녹을 예정인 치즈들을 공기(2)로 치환해준다.
  • 이번턴에 몇개의 치즈가 녹았는지 계산해준다.
• 마지막으로, 몇번의 턴이 걸렸는지, 마지막 턴에 몇개의 치즈가 녹았는지 출력

from collections import deque
dx=[0,0,1,-1]
dy=[1,-1,0,0]

mx,my=map(int,input().split())
count=[0,0,0]
cheeses=[]
li=[[0]*(my+1)]
for i in range(mx):
    tmp=[0]+list(map(int,input().split()))
    for j in range(1,my+1):
        if tmp[j]==1:
            cheeses.append([i,j])
    li.append(tmp)
    count[1]+=sum(tmp)

q=deque()
q.append((1,1))
while q:
    x,y=q.popleft()
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if 1<=nx<=mx and 1<=ny<=my:
            if li[nx][ny]==0:
                q.append((nx,ny))
                li[nx][ny]=2
tmp_c=0
while tmp_c<count[1]:
    q=deque()
    tmp_cc=0
    q.append((1,1))
    visit=[[0]*(my+1) for i in range(mx+1)]
    visit[1][1]=1
    tmp_airs=[]
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 1<=nx<=mx and 1<=ny<=my:
                if li[nx][ny]==0:
                    q.append((nx,ny))
                    li[nx][ny]=2
                    visit[nx][ny]=1
                elif li[nx][ny]==1 and visit[nx][ny]==0:
                    tmp_cc+=1
                    visit[nx][ny]=1
                    tmp_airs.append([nx,ny])
                elif li[nx][ny]==2 and visit[nx][ny]==0:
                    q.append((nx,ny))
                    visit[nx][ny]=1
    tmp_c+=tmp_cc
    count[2]=tmp_cc
    count[0]+=1
    for x,y in tmp_airs:
        li[x][y]=2
print(count[0])
print(count[2])