[맛있는물회] [파이썬] <백준 알고리즘> 2636, 2638번 "치즈"

문제 조건

---

N×M (5≤N, M≤100)의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

 

Input

---

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

 

Output

---

출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

 

생각한 아이디어

---

고전했던 부분이 내부 공기와 외부 공기를 구분하는 것이었다.

 

아이디어가 생각이 안났는데 제일 가장자리 부분은 치즈가 놓여질 수 없다는 말을 듣고 생각났다.

 

(0,0)으로부터 0인 부분을 다른 값으로 채워주면 구분이 가능하다!

 

하,., 그런데 간과한 점이 있다.

만약 내부 공기에 외부공기가 유입된다면 다시 aircheck을 해주어야하는데 이 부분을 while 안에서 시간이 지날때마다 모든 공기를 다시 bfs 하니깐 시간초과가 발생한다.

 

이 부분이 상당히 어려웠다. 

https://www.software.kr/download/?filePath=L7xCi_2FhV76fukwTQ5Ef3DoUmbR9UndWaKupGXqB5iRlQRuncnseSdG8NVUwWIlvGeAoho10r18rE_0AUcloX3JQvQ_3D_3D

창의적 알고리즘 (중급) 부분 치즈 부분의 힌트를 조금 얻어서 풀게되었다.

 

 

단순하게 반복적으로 air를 체크하는 것이 아닌, 공기로 바뀌는 치즈 부분을 list로 만들어서 이 부분만 다시 bfs를 수행했다.

 

이렇게 하니깐, 확실히 시간이 줄어들었다.

정답률 49프로가 믿기지 않는 문제이다. ㅎㅎ

2636, 2638번은 치즈가 없어지는 조건만 살짝 다르게 해준 동일한 문제이다.

 

BFS는 물론 DFS(BFS로도 이용가능) 을 아주 응용한 문제라서 쉽지 않았다.

 

소스코드

import sys
from collections import deque
import copy
input=sys.stdin.readline

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

def air_check(y,x,MAP,row,col):
   queue = deque()
   queue.append((y,x))
   while queue:
      y,x=queue.popleft()
      for dir in range(0,4):
         ny,nx=y+dy[dir],x+dx[dir]
         if row>ny>=0 and col>nx>=0 and MAP[ny][nx]==0:
            MAP[ny][nx]=-1
            queue.append((ny,nx))
   return MAP


def check(MAP,row,col):
   count=0
   tmp = copy.deepcopy(MAP)
   changes=[]
   for y in range(0,row):
      for x in range(0,col):
         if MAP[y][x]==1:
            flag = 0
            for dir in range(0,4):
               ny,nx=y+dy[dir],x+dx[dir]
               if row>ny>=0 and col>nx>=0 and MAP[ny][nx]==0:
                  if MAP[ny][nx]==-1: #공기 접촉
                     flag+=1
            if flag>=2:
               tmp[y][x]=-1 
               #치즈가 변경되는 부분으로 부터 aircheck를 해야하기떄문에 list를 만들어준다.
               changes.append([y,x])
               count+=1
   return tmp,count,changes

if __name__ == "__main__":
   row,col = map(int,input().split())
   MAP=[list(map(int,input().split())) for _ in range(row)]
   time,cnt2 = 0,0
   MAP = air_check(0,0,MAP,row,col) #맨첨에 바깥 공기를 구분한다.
   while 1:
      tmp,cnt,changes = check(MAP,row,col)
      if cnt==0:#치즈가 없다
         print(time)
         break
      else:
         MAP=tmp

      for change in changes:
         MAP = air_check(change[0],change[1],MAP,row,col)
      time+=1
      cnt2=cnt

 

*파이썬 문법 정리