치즈

문제 분석

외부 공기와 외부 공기로 둘러쌓인 치즈가 주어진다. 외부 공기와 접촉한 치즈는 한시간 후 녹아 없어진다. 그런데 치즈가 녹아 내부 공기가 외부 공기와 접촉하면, 이 공기도 외부 공기로 변하게 된다.

이때 치즈가 다 녹는데 걸리는 시간을 구하는 문제다.

내부 공기가 외부 공기로 변하는 시점을 파악하는 것이 중요하다. 그래서 내가 처음 생각한 방법은, 공기를 만날 때 마다 이 공기가 외부와 이어져 있는지 확인하는 것이었다.

  • BFS로 공기의 영역을 탐색하며 이 영역이 사각형의 끝까지 이어져있는지 확인했지만, 이 방식은 시간복잡도가 굉장히 높았다.

  • 또한, 한 시간씩 지날 때 마다, 리스트의 모든 점들을 살펴보며 치즈가 있는 지점을 탐색했다. 이 또한, 시간복잡도가 커서 시간초과를 발생시켰던 원인이었다.


이를 해결하기 위한 방법이, 치즈를 둘러싼 외부 공기만을 선택해 탐색해 나가는 방식이다. 아래의 그림을 보며 이해해보자. 0은 내부공기, ‘*‘은 외부공기로 표현했다.

Crepe

  • 먼저 최초의 외부 공기를 BFS로 찾아낸다.
  • 이 공기들과 인접한 치즈들을 모두 녹여 ‘*‘로 변환한다.
  • 인접한 치즈들 외에도 외부 공기와 접촉하게 된 내부공기도 ‘*‘로 변환한다.
  • 이 과정을 반복한다.


CODE

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

h,w=map(int,read().split())
ch=list(list(map(int,read().split())) for _ in range(h))

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

point=deque([[0,0]])
outsideair=[]#치즈를 감싸는 공기 저장

while point:
    a,b=point.popleft()
    for x,y in zip(dx,dy):
        ax,by=a+x,b+y
        if 0<=ax<h and 0<=by<w and ch[ax][by]==0:
            point.append([ax,by])
            ch[ax][by]='*'
            #리스트를 프린트했을 때 사각형이 깨지지 않도록 하기위해 -1이 아닌 *로 변환했다.
            outsideair.append([ax,by])

time=0#치즈가 사라질때 까지 걸린 시간
disappear_tmp=0#이전 회차에서 사라진 치즈의 개수 저장
disappear=0#이번 회차에서 사라질 치즈의 개수

while True:
    disappear_tmp=disappear
    disappear=0
    outsideair_tmp=[]#치즈가 없어져 새로운 외부공기가 될 칸들을 저장

    #outsideair에 둘러쌓인 없어질 치즈들 탐색
    for a,b in outsideair:
        for x,y in zip(dx,dy):
            ax,by=a+x,b+y
            if 0<=ax<h and 0<=by<w and ch[ax][by]==1 and [ax,by] not in outsideair_tmp:
                outsideair_tmp.append([ax,by])
                disappear+=1

    tmp=[]
    #outsideair에 둘러쌓여 없어질 치즈들을 탐색한 후
    #치즈들이 녹고 나서 내부 공기가 외부 공기와 만날 수도 있기 때문에, 이런 공기들을 다시한번 탐색해 tmp에 저장한 후 outsideair_tmp에 추가해준다.
    for a,b in outsideair_tmp:
        ch[a][b]='*'
        point=deque([[a,b]])
        while point:
            a,b=point.popleft()
            for x,y in zip(dx,dy):
                ax,by=a+x,b+y
                #녹은 치즈들과 인접한 공기가 존재하면 이 공기들도 '*'로 변환
                if 0<=ax<h and 0<=by<w and ch[ax][by]==0:
                    point.append([ax,by])
                    ch[ax][by]='*'
                    tmp.append([ax,by])

    outsideair_tmp+=tmp
    outsideair=outsideair_tmp[::]
    #녹은 치즈가 없다면 while문 탈출!
    if outsideair==[]:
        print(time)
        print(disappear_tmp)
        break

    time+=1


CODE - 처음에 시도했던 코드(시간 초과)

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

h,w=map(int,read().split())
ch=list(list(map(int,read().split())) for _ in range(h))

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

def outside_air(i,j):
    point=deque([[i,j]])
    save=[[i,j]]
    while point:
        a,b=point.popleft()
        for x,y in zip(dx,dy):
            ax,by=a+x,b+y
            if 0<=ax<h and 0<=by<w and ch[ax][by]==0 and [ax,by] not in save:
                if ax==0 or ax==h-1 or by==0 or by==w-1:
                    return True
                point.append([ax,by])
                save.append([ax,by])
    return False

def will_melt(a,b):
    for x,y in zip(dx,dy):
        ax,by=a+x,b+y
        if 0<=ax<h and 0<=by<w and ch[ax][by]==0:
            if outside_air(ax,by): return True
    return False

answer=0
while True:
    save=[]
    for i in range(h):
        for j in range(w):
            if ch[i][j]==1 and will_melt(i,j):
                save.append([i,j])
    if save==[]:
        print(answer)
        print(save_tmp)
        break
    for a,b in save:
        ch[a][b]=0
    answer+=1
    save_tmp=len(save)

틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]