[코테] 치즈

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

2638번: 치즈

문제요약: 

2차원 모눈종이 위에 0은에는 아무것도 없고, 1은 치즈를 나타낸다. 1초가 지날 때 마다 치즈에서 4면이 밖에 맞닿아 있을 경우 , 치즈는 녹아 사라지게 된다. 이때 밖이라는 경우는 예를들어

다음과 같이 치즈로 감싸져 있지 않은 부분을 의미하며 만약 치즈로 감싸져 있다면 치즈가 없어도 이는 밖이라고 치지 않는다. 가장자리에는 치즈가 주어지지 않는다고 할 때, 치즈가 모두 녹아 없어지는데 걸리는 시간을 출력하시오.

 

소요시간:

22분

 

난이도:

골드3

 

제출횟수:

1회

 

코딩:

import sys
input = sys.stdin.readline
from collections import deque
n,m = map(int,input().split())
arr= [list(map(int,input().split())) for _ in range(n)]

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

def bfs_findout():
    out = set([(0,0)])
    q = deque([[0,0]])
    while q:
        y,x = q.popleft()
        for i in range(4):
            ny = y +dy[i]
            nx = x +dx[i]
            if 0<=ny<n and 0<=nx<m and arr[ny][nx] == 0 and (ny,nx) not in out:
                #밖이고,온적없다
                out.add((ny,nx))
                q.append((ny,nx))
    return out

while True:
    out = bfs_findout()
    vanishing_list = []
    for y in range(n):
        for x in range(m):
            if arr[y][x] == 1 :
                #치즈라면
                piv = 0
                for i in range(4):
                    ny = y +dy[i]
                    nx = x +dx[i]
                    if 0<=ny<n and 0<=nx<m and (ny,nx) in out:
                        piv +=1
                        #만약 범위 내에 있고 상하좌우중 밖이 있다면
                if piv >=2 :
                    #만약상화좌우중 밖이 두개 이상이라면
                    vanishing_list.append([y,x])
    if vanishing_list:
        ans +=1
        for y,x in vanishing_list:
            arr[y][x] = 0
    else:
        print(ans)
        break

가장 자리는 치즈가 있지 않다는 점을 이용해 밖을 구하는것을 먼저 구현했습니다. [0,0]은 가장자리이기 떄문에 무조건 치즈가 존재하지 않고 이와 이어지는 공간이라면 무조건 치즈 밖이고 이가 아니라면 치즈가 없어도 치즈안으로 둘러쌓인 공간이라는 것을 알 수 있습니다. 그래서 bfs로 매번 치즈밖을 구해 out이라는 set에 저장해두고, 전체를 돌며 치즈인곳에서 만약 양옆이 밖이라면 이를 vanishing_list에 저장해두었다가 이를 지워주었습니다.

이때 항상 전체를 돌지않고 치즈가 있는곳만 기억해두었다가 지워주어 시간을 절약할 수 도있습니다.