Python-2638-치즈

🧀치즈  click

두 달 만에 풀 수 있었다.

이 문제도 두 달에 걸쳐 시도했지만, 풀지 못했던 문제였다. 두달여 만에 시도했더니 생각보다 수월하게 풀 수 있었다. 그새 실력이 성장한 것 같다. 앞으로도 꾸준히 풀어나가자!

 

 

문제 분석

 

문제를 풀면서 가장 고민이었던 부분 두 가지는, 내부 공기를 어떻게 처리해야 하는지와 치즈들을 어떻게 탐색해 나갈지 였다.

 

 

내부 공기

 

먼저, 내부 공기와 외부 공기를 다른 문자(혹은 숫자)로 표시한다.

녹을 치즈들에 대해 내부 공기와 동일한 문자로 변경해둔다.

한 사이클을 모두 돌고난 후에 녹은 치즈들을 시작으로 BFS탐색을 하며 외부 공기와 닿은 내부 공기도 모두 외부 공기로 변경한다.

 

 

치즈 탐색

 

치즈들을 모두 deque에 추가해둔 후에, 각 치즈들에 대해 탐색을 한다.

이때, 녹은 치즈면 deque에 추가하지 않고, 녹지 않은 치즈면 다시 deque에 추가해주며 탐색해야 하는 치즈들에 대한 정보를 유지할 수 있었다.

 

 

 

외부와 내부 공기가 구분되어 있다.

 

치즈가 공기와 접촉하면 천천히 녹는다. 이때, 치즈의 4변 중에서 적어도 2변 이상이 외부 공기와 접촉하면 한시간만에 녹아 없어진다. 이때, 치즈 내부에 있는 공기와는 접촉해도 녹지 않는다. 따라서, BFS를 진행할 때, 외부 공기와 내부 공기를 나누어 생각해주어야 한다!

 

 

문제 해설에 사용될 입력 예제

input:

8 9
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 1 1 0
0 1 0 1 1 1 0 1 0
0 1 0 0 1 0 0 1 0
0 1 0 1 1 1 0 1 0
0 1 1 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0

answer: 3

 

 

 

외부 공기와 내부 공기를 구분해주기 위해서 외부 공기는 '*'로, 내부 공기는 0으로 표시했다.

모눈종이의 가장자리에는 치즈가 놓이지 않음으로 [0,0]은 반드시 외부 공기이다. 따라서, [0,0]부터 BFS를 진행해 외부 공기를 모두 '*'로 바꾸어 주었다.

이렇게 되면 아래와 같은 모양을 이루게 된다.

 

 

 

이제, 치즈를 녹혀보자.

 

치즈가 녹는 과정

 

 

위의 그림애서 빈 칸은 '*' 이 저장되어 있는 칸이다. 가독성을 위해 빈 칸으로 두었다.

 

• 치즈가 존재하는 칸의 좌표를 deque에 모두 저장해 놓는다.
• deque를 사용해 BFS를 진행한다. 이때, '*'(외부 공기)와 두 면 이상 닿은 점만 녹는다.
• 녹은 공간을 바로 '*'로 변경하게 되면, 그 다음 칸을 탐색할 때 영향을 받게된다. 따라서, 녹은 자리를 우선 0으로 변경해 놓고, 녹은 치즈들을 별도의 배열에 저장한다.
• 치즈들을 모두 탐색하고 나서, 배열에 저장된 좌표들에 대해 BFS탐색을 진행한다. 
• 단순히 0을 '*'로 변경하는 것이 아니라, BFS탐색을 다시 진행하는 이유는 접촉해 있는 내부 공기도 외부 공기로 변경해주기 위함이다.

 

 

Code

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

#0이 저장되어 있는 공간(내부 공기)를 '*'(외부 공기)로 변경
def outside_air(a,b):
    MAP[a][b] = '*'
    point = deque([(a,b)])
    while point:
        a,b = point.popleft()
        for x,y in [(1,0),(0,1),(-1,0),(0,-1)]:
            ax, by = a+x, b+y
            if MAP[ax][by] == 0:
                MAP[ax][by] = '*'
                point.append((ax,by))


def bfs():
    point = deque([])
    for i in range(n):
        for j in range(m):
            if MAP[i][j] == 1:
                point.append((i,j))

    time = 0
    while point:
        #녹을 치즈들의 좌표를 저장
        isMelt = []
        for _ in range(len(point)):
            a,b = point.popleft()
            air = 0
            for x,y in [(1,0),(0,1),(-1,0),(0,-1)]:
                ax,by = a+x, b+y
                if MAP[ax][by] == '*':
                    air+=1
                if air >=2:
                    isMelt.append((a,b))
                    #바로 '*'로 변경하게 되면 주변 점이 영향을 받게 된다.
                    #우선 0으로 변경 후, 한 사이클이 끝나고 내부공기와 함께 '*'로 변경
                    MAP[a][b] = 0
                    break
            #녹지 않았다면, 다음 사이클에 속할 수 있도록 deque에 다시 추가한다.
            else: point.append((a,b))

        if isMelt:
            #녹을 치즈들 주변의 내부 공기까지 모두 '*'으로 변경
            for a,b in isMelt:
                outside_air(a,b)
        time += 1
        
    return time

n,m = map(int,read().split())
MAP = list(list(map(int,read().split())) for _ in range(n))
outside_air(0,0)

print(bfs())

 

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

[꼭 다시 풀어보기]