2636: 치즈

풀이 시간

• 22m
• 무난한 bfs 탐색 문제였다

구현 방식

• 처음에는 치즈를 시작노드로 하여 bfs 탐색을 하면서 'c'를 표시해야겠다고 생각했으나, 구현 방법을 떠올리기가 쉽지 않았다. 이 문제에선 "판의 가장자리에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구명이 있을 수 있다."라는 조건이 핵심이었던 것 같다
  -> 발상을 전환하여 가장 왼쪽 위는 무조건 빈 공간이기 때문에 해당 위치에서 부터 bfs 탐색을 시작하여 녹는 부분을 'c'로 변경해주는 방식으로 구현해주었다
• bfs의 반환값을 c_board (c로 변경된 격자의 좌표들)로 설정해주었다

코드

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[x][y] = True

    c_board = []

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]; ny = y + dy[i]
            if 0 <= nx < R and 0 <= ny < C:
                if board[nx][ny] == 0 and not visit[nx][ny]:
                    visit[nx][ny] = True
                    queue.append((nx, ny))
                elif board[nx][ny] == 1 and not visit[nx][ny]:
                    visit[nx][ny] = True
                    board[nx][ny] = 'c'
                    c_board.append((nx, ny))
    
    return c_board

def c_remove(c_board):
    for x, y in c_board:
        board[x][y] = 0


R, C = map(int, sys.stdin.readline()[:-1].split())
board = []
for r in range(R):
    board.append(list(map(int, sys.stdin.readline()[:-1].split())))

turn = 0; c_cnt = 0
while True:
    #가장 왼쪽위는 무조건 빈 공간임 여기서에 bfs를 시작하여 녹는 부분을 c로 바꿔줌
    visit = [[False] * C for _ in range(R)]
    c_board = bfs(0, 0)

    if not c_board:
        break

    c_cnt = len(c_board)

    #치즈조각 녹이기
    c_remove(c_board)

    turn += 1



print(turn)
print(c_cnt)

결과