[ALGO/Python] 2636. 치즈

001. 생각 정리

목표: BFS를 한 번만 수행하여 매 회차의 치즈 경계선 파악하기

1. 매 회차 좌측 상단 모서리에서 BFS를 수행하여 치즈의 경계선을 파악하였습니다.

   1. 특정 좌표에서 4방향(북, 동, 남, 서) 탐색을 실시하여 값이 "1"인 좌표를 발견하면, 경계선 처리를 하였습니다.

2. 매 회차의 결과를 저장하는 리스트를 할당하여 사용하였습니다.

   1. 경계선을 파악한 후 해당 회차의 남아 있는 치즈 크기를 계산하여 회차 정보와 함께 결과 리스트에 추가하였습니다.

3. 문제에서 요구하는 대로 결과 리스트에서 필요한 값만 인덱싱하여 출력하였습니다.
   
   

001.1. 치즈 경계선 파악

문제에서 주어진 입력값을 보면 "0"으로 패딩 처리가 되어 있습니다. 따라서 항상 (0, 0) 좌표의 값은 "0"일 수밖에 없으며, 해당 좌표에서부터 BFS를 수행한다면, 치즈 외부의 영역만 탐색하면서 치즈 경계선을 파악할 수 있습니다. 치즈 경계선은 외부 영역에서 탐색했을 때 맞닥뜨린, 값이 "1"인 좌표들입니다. 치즈 경계선의 좌표는 큐에 넣어주지 않고 값을 "0"으로 재할당하였습니다.

001.2. 남은 치즈 크기 계산

치즈를 표현하는 2차원 리스트는 "0"과 "1"로만 구성되어 있습니다. 값 "1"이 의미하는 바가 치즈이므로 합산(sum)을 활용하였으며, 2차원 리스트 전체 합을 편하게 구하기 위해 맵(map)도 적용하였습니다.

002. 코드

import sys
from collections import deque


def check_default_cond(row, col, visited):
    return True if 0 <= row < R and 0 <= col < C and not visited[row][col] else False


def check_border():
    # 1. 좌측 상단 모서리에서 BFS 수행 및 치즈 경계선 파악
    q = deque([(0, 0)])
    visited = [[False] * C for _ in range(R)]
    visited[0][0] = True

    while q:
        row, col = q.popleft()

        for d in range(4):
            nrow, ncol = row + dy[d], col + dx[d]
            if check_default_cond(nrow, ncol, visited):
                visited[nrow][ncol] = True

                # 1.1. 경계선 처리
                if BOARD[nrow][ncol] == 1:
                    BOARD[nrow][ncol] = 0
                else:
                    q.append((nrow, ncol))


def count():
    return sum(map(sum, BOARD))


R, C = map(int, sys.stdin.readline().split())
BOARD = [list(map(int, sys.stdin.readline().split())) for _ in range(R)]

dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
result = [(0, count())]  # 2. 매 회차의 결과를 저장하는 리스트

while result[-1][1]:
    check_border()
    result.append((result[-1][0] + 1, count()))

# 3. 문제에서 요구하는 값만 인덱싱
print(result[-1][0])
print(result[-2][1])

End