2638: 치즈

풀이 시간

• 16m
• 무난한 bfs 문제

구현 방식

• 모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정하기 때문에 매 turn 마다 bfs(0, 0)을 호출하여 'C'를 구한다

• C의 좌표를 구하는 과정에서, "모눈종이 모양의 치즈에서 각 치즈 격자(작은 정사각형 모양)의 4번 중에서 적어도 2번 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다."라는 조건을 바탕으로 접촉이 발생할 경우마다 board[nx][ny]에 1을 더해준다
  -> board[i][j]가 3 이상이라면 'C'이다

• remove(C)를 호출하여 'C'를 없앤다 (C가 None이면 종료)

코드

import sys
from collections import deque

dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)

def bfs(x, y):
    queue = deque([]); queue.append((x, y))
    visit = [[False] * M for _ in range(N)]
    visit[x][y] = True
    C_coor = []

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]; ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if board[nx][ny] == 0 and not visit[nx][ny]:
                    visit[nx][ny] = True
                    queue.append((nx, ny))
                if board[nx][ny] != 0:
                    board[nx][ny] += 1

    for i in range(N):
        for j in range(M):
            if board[i][j] >= 3:
                C_coor.append((i, j))
            elif board[i][j] == 2:
                board[i][j] = 1
    return C_coor

def remove(C):
    for x, y in C:
        board[x][y] = 0
    

N, M = map(int, sys.stdin.readline()[:-1].split())
board = []
for n in range(N):
    board.append(list(map(int, sys.stdin.readline()[:-1].split())))

turn = 0
while True:
    ##### 'C' 구하기
    C = bfs(0, 0)

    ##### 반환받은 'C'의 좌표가 없다면 종료
    if not C:
        break

    ##### 'C' 제거
    remove(C)

    turn += 1

print(turn)

결과