[백준] 2638. 치즈 - Python

[Gold III]

 

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

2638번: 치즈

 

풀이

"두 변 이상 치즈 외부 공기와 접촉" 한다는 조건만 잘 처리해 준다면,

N, M (5 ≤ N, M ≤ 100) 이기 때문에 나머지는 Brute-Force로 처리해도 해결되는 문제이다.

 

air 2차원 배열을 생성하여, 모든 칸을 순회하며, 외부 공기와 접촉한 공기 칸을 체크한다.

이 때, air 배열의 모든 칸은 1로 초기화하고, 외부와 닿아 있는 공기 칸일 시,

그 칸부터 BFS를 통해, 이어진 모든 공기 칸을 air 배열에 체크한다.

 

그 이후는, 그저 모든 칸을 순회하며, 주위 4칸 중 air 배열에 체크된 칸(외부 공기와 통하는 공기 칸)이 2개 이상인 지 확인하고,

그렇다면 치즈를 녹여주면 된다.

 

이 과정을 계속 반복하여, 모든 치즈를 녹일 때까지 반복하면 성공.

자세한 흐름을 주석을 참조.

 

AC.

from collections import deque
 
N, M = map(int, input().split())
 
p = []
for _ in range(N):
    p.append(list(map(int, input().split())))
    
dr = [1, 0, -1, 0]
dc = [0, 1, 0, -1]
 
air = [[1]*M for _ in range(N)]
 
def BFS(r, c):
    deq = deque([(r, c)])
    while deq:
        nr, nc = deq.popleft()
        for i in range(4):
            lr = nr+dr[i]
            lc = nc+dc[i]
        
            # 격자 벗어남 체크 / 공기 칸인지 체크 / bfs에서 이미 지나간 칸인 지 확인 (air[lr][lc])
            if 0 <= lr < N and 0 <= lc < M and p[lr][lc] == 0 and air[lr][lc] == 1:
                air[lr][lc] = 0
                deq.append((lr, lc))
 
T = 0   # 걸린 시간
while True:
    T += 1
    air = [[1]*M for _ in range(N)]
    
    # 공기가 확산되는 칸을 check.
    for r in range(N):
        for c in range(M):
            # 치즈가 있는 칸이거나, 이미 외부 공기와 통한다고 체크한 칸은 pass.
            if p[r][c] == 1 or air[r][c] == 0:
                continue
            
            # 현재 칸이 외부와 닿아 있으면 isAirExposed = True.
            isAirExposed = False
            for i in range(4):
                lr = r+dr[i]
                lc = c+dc[i]
                if lr < 0 or lr >= N or lc < 0 or lc >= M:
                    isAirExposed = True
                    break
            
            # 외부와 맞닿은 칸부터 BFS로 공기인 칸을 탐색하며 외부 공기와 통하는 것으로 check (0으로 변경)
            if isAirExposed:
                BFS(r, c)
 
    # 치즈 녹이기
    for r in range(N):
        for c in range(M):
            if p[r][c] == 0:
                continue
            
            cnt = 0
            for i in range(4):
                lr = r+dr[i]
                lc = c+dc[i]
                if air[lr][lc] == 0:
                    cnt += 1
            # 외부 공기와 2변 이상 닿으면, 치즈를 녹인다.
            if cnt >= 2:
                p[r][c] = 0
 
    # 다 녹음 체크
    isAllMelt = True
    for r in range(N):
        if not isAllMelt:
            break
        for c in range(M):
            if p[r][c] == 1:
                isAllMelt = False
                break
    
    if isAllMelt:
        print(T)
        break