1 minute read

접근 방법

처음에는 내부 공기를 정의하고 이 내부 공기와 접촉한 경우는 제외하려고 했다. 하지만 그럴 경우 모든 case를 다 정의해야 하고 가능할 거 같지도 않았다. 더 생각해보니 치즈 블록을 지나갈 수 없는 벽이라고 생각했을 때, 외부에서 bfs를 하여 치즈 블록에 닿은 경우의 수를 기록하면 몇 칸의 외부 공기와 닿은지 알 수 있다는 것을 알았다.

  1. 외부공기에서 bfs를 시작해서 똑같은 외부 공기라면 다음 조사 대상 (queue)에 저장
  2. 치즈 블록에 닿았다면 그 횟수를 visited 배열에 저장하였다.
  3. 닿은 횟수가 2회 이상인 치즈 좌표(녹을 예정)들과 개수를 저장했다.
  4. 녹을 예정인 치즈들의 maps에서의 값을 0으로 초기화하여 녹은걸 update 했음
  5. 이 과정을 총 치즈 개수가 0일 때까지 반복

정답 코드


import sys
from collections import deque

input = sys.stdin.readline
n,m = map(int, input().split())
maps = []
for _ in range(n):
    maps.append(list(map(int, input().split())))


"""
외부공기의 닿음을 표현하기 위해서는 치즈가 놓인 곳은 지나가지 못하게 하면 된다
외부공기가 닿은 곳을 저장하고 그 곳들을 0으로 초기화하는 과정을 반복하면 된다.
이때 while 문의 종료 조건을 위해 cheese 개수를 가지고 외부공기가 2번 이상 닿은 곳 개수만큼 빼기
"""
total_cheese = 0
for i in range(n):
    for j in range(m):
        if maps[i][j] == 1:
            total_cheese += 1

moves = [(1,0), (0,-1), (0,1), (-1,0)]

time = 0
def bfs(start_h, start_w):
    q = deque()
    #visited 배열에 외부공기와 접촉 횟수를 저장
    visited = [[0]*(m) for _ in range(n)]
    q.append((start_h, start_w))
    visited[start_h][start_w] = 1
    while q:
        h,w = q.popleft()
        for dh,dw in moves:
            new_h, new_w = h+dh, w+dw
            if 0<=new_h<n and 0<=new_w<m:
                if maps[new_h][new_w] == 0 and visited[new_h][new_w] == 0:
                    visited[new_h][new_w] = 1
                    q.append((new_h, new_w))
                #치즈라면
                elif maps[new_h][new_w] == 1:
                    visited[new_h][new_w] += 1

    melts = []
    will_melt = 0
    for i in range(n):
        for j in range(m):
            if visited[i][j] >= 2:
                melts.append((i,j))
                will_melt += 1
    
    return melts, will_melt


while total_cheese:
    h,w = 0,0
    melts, will_melt = bfs(0,0)
    for y,x in melts:
        maps[y][x] = 0
    total_cheese -= will_melt
    time += 1

print(time)

You May Also Enjoy