[ 백준 2636 ] 치즈 - Python

문제 보기

이 문제는 BFS이다.

 

개인적으로 골드 5 난이도에서 가장 어려웠다.  BFS를 구현하는 것은 어렵지 않았으나, BFS를 적용하기 위해서 가장 바깥쪽 테두리를 파악하는 게 핵심이었다.

 

처음에는 단순하게 적용하였다. 상, 하, 좌, 우를 살펴보면서 0이 있으면 가장 바깥쪽이다라고 생각하고 구현하였지만 틀렸다. 그 이유는 내부 0과 외부 0을 구별하지 못했기 때문이다.

 

따라서 내부 0과 외부 0을 구별하기 위해서 총 2단계의 BFS를 진행하였다. (0, 0)은 무조건 외부 0이기 때문에 (0, 0)을 큐에 넣은 후 연결된 모든 0을 -1로 바꿔줌으로써 내부 0과 외부 0을 구별하였다.

 

알고리즘 순서를 정리하자면 아래와 같다.

1. 외부와 내부 0을 구분한다.

2. 치즈를 모두 담은 큐를 대상으로 bfs를 진행한다.

3. 상, 하, 좌, 우에 외부 0(-1)이 있다면 제거하고 아니라면 유지시킨다.

  - 외부 0(-1)이 있다면 bfs를 진행한 후 현재 위치 값을 -1로 수정한다. (바깥쪽 제거)

4. 위 과정을 치즈가 모두 사라질 때까지 진행한다.

 

코드

from collections import deque


def division_bfs():
    q = deque([[0, 0]])
    visited = {(0, 0)}

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

        for r, c in [(-1, 0), (1, 0), (0, -1), (0, 1)]:  # 상, 하, 좌, 우
            new_row, new_col = row + r, col + c
            if 0 <= new_row < y and 0 <= new_col < x:
                if arr[new_row][new_col] == 0 or arr[new_row][new_col] == -1 and (new_row, new_col) not in visited:
                    arr[new_row][new_col] = -1
                    q.append([new_row, new_col])
                    visited.add((new_row, new_col))


def bfs():
    change, temp = [], []
    while cheese:
        row, col = cheese.popleft()
        if arr[row - 1][col] == -1 or arr[row + 1][col] == -1 or arr[row][col - 1] == -1 or arr[row][col + 1] == -1:
            change.append([row, col])
        else:
            temp.append([row, col])

    cheese.extend(temp)
    if len(cheese) > 0:
        for r, c in change:
            arr[r][c] = -1
        return 1
    return 0


if __name__ == "__main__":
    # input
    y, x = map(int, input().split())  # 세로, 가로
    arr = [list(map(int, input().split())) for _ in range(y)]

    # 치즈 리스트 생성
    cheese = deque([])
    for i in range(y):
        for j in range(x):
            if arr[i][j] == 1:  # 치즈가 있으면
                cheese.append([i, j])

    time, area = 0, len(cheese)
    while cheese:
        time += 1
        # 외부와 내부 0 구분
        division_bfs()
        bfs()
        if len(cheese) != 0:
            area = len(cheese)

    print(time)
    print(area)