[Python] 백준 2638번: 치즈

https://www.acmicpc.net/problem/2638

2638번: 치즈

 

import sys

input = sys.stdin.readline
AIR, CHEESE = 0, 1
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def getMinTime():
    minTime = 0

    while meltCheese():
        minTime += 1

    return minTime


def meltCheese():
    outerPositions = [(i, 0) for i in range(N)] + [(i, M-1) for i in range(N)] +\
        [(0, j) for j in range(1, M-1)] + [(N-1, j) for j in range(1, M-1)]
    isVisited = [[False]*M for _ in range(N)]

    for ox, oy in outerPositions:
        if isVisited[ox][oy] == True:
            continue

        isVisited[ox][oy] = True

        if grid[ox][oy] == AIR:
            todo = [(ox, oy)]

            while todo:
                x, y = todo.pop(0)

                for i in range(4):
                    nx, ny = x + dx[i], y + dy[i]

                    if 0 <= nx <= N-1 and 0 <= ny <= M-1:
                        adj = grid[nx][ny]

                        if isVisited[nx][ny] == False and adj == AIR:
                            todo.append((nx, ny))
                            isVisited[nx][ny] = True
                        elif adj >= CHEESE:
                            grid[nx][ny] += 1
        else:
            grid[ox][oy] += 1

    # 치즈 녹이기, 치즈 1로 초기화
    flag = False
    for i in range(N):
        for j in range(M):
            n = grid[i][j]

            if n >= 3:
                grid[i][j] = 0
                flag = True
            elif n == 2:
                grid[i][j] = 1

    return flag


if __name__ == '__main__':
    N, M = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(N)]

    minTime = getMinTime()
    print(minTime)

 

'치즈 외부 공기'와 '치즈 내부 공기'가 나뉘어있으므로, 외부 공기를 위주로 탐색을 한다. 가장 바깥 라인의 공기는 무조건 외부 공기이므로 해당 좌표들(outerPositions)을 기준으로 BFS 탐색을 시작한다.

만약 가장 바깥 라인이 치즈일 경우, 이것도 외부 공기와 접촉한 것이므로, 이에 대해 조건문을 작성한다.

BFS 탐색은 인접 공기들을 통해 탐색을 계속해간다. 또한, 인접 노드가 치즈일 경우에는 입력받은 grid값을 1 증가시킨다. 즉, 해당 치즈가 외부 공기와 닿을 때마다 카운트를 해준다는 것이다.

 

이렇게 탐색이 끝나면, 외부 공기로 인해 카운트된 값이 3 이상일 경우 치즈를 녹인다. 또 flag를 True로 설정해주는데, 이것은 치즈를 1번이라도 녹였다는 것을 의미한다. 만약 flag가 False로 함수가 끝나면, 녹일 치즈가 없다는 것이므로 이 함수(meltCheese())를 더이상 수행하지 않게끔 한다. 그리고, 외부 공기에 얼마나 노출되었는지를 grid에 임의로 기록하였기 때문에, 이것을 다시 원상태로 돌려놓아야한다.

 

중요한 테스트 케이스는 아래와 같다.

5 9
0 1 1 0 0 0 1 1 0
0 1 0 1 1 1 0 1 0
0 1 0 0 1 0 0 1 0
0 1 0 1 1 1 0 1 0
0 1 1 0 0 0 1 1 0