[백준 알고리즘] 2636.치즈

 

 

 

 

안에 구멍이 있는 경우는 바깥과 연결되어야 녹일 수 있으므로, 

 

핵심은 바깥(외부)을 찾는 것이 중요했다.

 

그래서  2가지 구조로 나눠

바깥을 체크하고 -> 체크한 바깥과 닿아있는 치즈를 녹이기 -> 다시 바깥을 체크(이때는 녹은치즈 + 새로 생긴 구멍) -> 녹은치즈 이런식으로 체크했다.

 

 

 

from collections import deque

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

# 바깥 체크
def outside():
    while Q:
        row, col = Q.popleft()
        arr[row][col] = -1
        for dt in range(4):
            new_row = row + delta[dt][0]
            new_col = col + delta[dt][1]
            if 0 <= new_row < r and 0 <= new_col < c and arr[new_row][new_col] == 0:
                arr[new_row][new_col] = -1
                Q.append((new_row, new_col))
    melt_cheese()
    return

# 치즈 녹이기
def melt_cheese():
    cnt = 0
    for row in range(r):
        for col in range(c):
            if arr[row][col] == 1:
                if arr[row-1][col] == -1:
                    arr[row][col] = 0 # 녹은 치즈
                    Q.append((row, col))
                    cnt += 1
                    continue
                if arr[row+1][col] == -1:
                    arr[row][col] = 0  # 녹은 치즈
                    Q.append((row, col))
                    cnt += 1
                    continue
                if arr[row][col-1] == -1:
                    arr[row][col] = 0  # 녹은 치즈
                    Q.append((row, col))
                    cnt += 1
                    continue
                if arr[row][col+1] == -1:
                    arr[row][col] = 0  # 녹은 치즈
                    Q.append((row, col))
                    cnt += 1
                    continue
    if cnt == 0:
        return
    else:
        time.append(cnt)
        outside()

r, c = map(int, input().split())
arr = []
time = [0]
for _ in range(r):
    arr.append(list(map(int, input().split())))

Q = deque([(0, 0)])
outside()
N = len(time)-1
print(N)
print(time[N])