[백준 2638] 치즈 - Python

문제 보기

[사용한 알고리즘]

BFS(너비 우선 탐색), 구현

 

[문제 접근]

세 단계 과정을 통해 문제를 구현하고자 하였습니다. 첫째, 주어진 N x M 모눈종이에서 외부 공기 위치를 구합니다. 둘째, 각 치즈 상, 하, 좌, 우에 인접한 외부 공기 위치 개수를 파악합니다. 셋째, 외부 공기가 2개 이상인 치즈를 녹입니다. 위 과정을 모든 치즈가 녹을 때까지 진행합니다.

 

[알고리즘]

1. 외부 공기 위치를 구합니다. (맨 가장자리를 출발점으로 BFS 탐색을 하여 외부 공기를 파악합니다)

2. 각 치즈의 인접한 외부 공기 위치 개수를 구합니다.

3. 외부 공기가 2개 이상인 치즈를 녹입니다.

4. 위 과정을 모든 치즈가 녹을 때까지 반복합니다.

 

[코드]

from collections import deque
import sys

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def outer(r, c, visited):
    q = deque()
    q.append((r, c))

    while q:
        x, y = q.popleft()
        visited.add((x, y))
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if maps[nx][ny] != 1 and (nx, ny) not in visited:
                    visited.add((nx, ny))
                    q.append((nx, ny))


if __name__ == "__main__":
    n, m = map(int, sys.stdin.readline().split())
    maps = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
    t = 0
    while True:
        # 외부 공기 구별
        visited = set()
        for i in range(n):
            if maps[i][0] != 1:
                outer(i, 0, visited)
        for i in range(n):
            if maps[i][m - 1] != 1:
                outer(i, m - 1, visited)
        for i in range(m):
            if maps[0][i] != 1:
                outer(0, i, visited)
        for i in range(m):
            if maps[n - 1][i] != 1:
                outer(n - 1, i, visited)
        for i, j in visited:
            maps[i][j] = 2

        cnt = 0  # 치즈 개수
        for i in range(n):
            for j in range(m):
                # 가장 자리 제외
                if (i == 0 and j == 0) or (i == 0 and j == m - 1) or (i == n - 1 and j == 0) or (
                        i == n - 1 and j == m - 1) or maps[i][j] != 1:
                    continue
                cnt += 1
                outer_cnt = 0
                # 외부 공기 개수 파악(상, 하, 좌, 우)
                if i - 1 >= 0 and maps[i - 1][j] == 2:  # 상
                    outer_cnt += 1
                if i + 1 < n and maps[i + 1][j] == 2:  # 하
                    outer_cnt += 1
                if j - 1 >= 0 and maps[i][j - 1] == 2:  # 좌
                    outer_cnt += 1
                if j + 1 < m and maps[i][j + 1] == 2:  # 우
                    outer_cnt += 1
                if outer_cnt >= 2:
                    maps[i][j] = 0  # 치즈 제거
        if cnt == 0:
            break
        t += 1

    print(t)