✅ BOJ 2638 - BFS 응용

문제 요약

외부 공기랑 두 면 이상 맞닿으면 치즈가 녹음. 내부에 갇힌 공기는 외부 공기 취급 안 함. 치즈 다 없어질 때까지 시간 세서 출력하면 끝임.

외부 공기 구분

매 라운드마다 (0,0)에서 BFS 돌려서 외부 공기만 True로 마킹해둬야 함. 내부에 갇힌 0까지 외부로 쳤다간 바로 오답행.

치즈 녹이기 로직

그리드 전체 순회하면서 치즈(1) 만나면 사방 다 확인해서 외부공기랑 닿는 면 몇 개인지 세라. 두 개 이상이면 그 칸 이번 라운드에서 바로 녹인다. 그 외에는 신경 꺼도 됨.

반복 & 종료

한 번 돌릴 때마다 시간+1 하고, 치즈 다 사라지면 그때 while문 끝내고 시간만 출력하면 됨. for문 중간에 break, else 쓰면 상태 꼬이니까 그런 거 쓰지 말고 네 방향 다 확인한 뒤에 처리하기.

---

BFS여서 아이디어 자체는 어렵지 않았던 문제. 구현이 귀찮았음.

# bfs: 외부공기 라운드마다 판별하기
from collections import deque
import sys
input=sys.stdin.readline

# 매 라운드마다 외부 공기인지, 내부 공기인지를 판별합니다.
def bfs_outer_air(grid):
    start_y,start_x=0,0
    directions=[(0,1),(-1,0),(0,-1),(1,0)]
    row=len(grid)
    col=len(grid[0])
    
    outer_air=[[False]*col for _ in range(row)]
    outer_air[start_y][start_x]=True
    q=deque()
    q.append((start_y,start_x))
    
    while q:
        cy,cx=q.popleft()
        
        for dy,dx in directions:
            ny=cy+dy
            nx=cx+dx
            if 0<=ny<row and 0<=nx<col:
                if outer_air[ny][nx]==False and grid[ny][nx]!=1:
                    outer_air[ny][nx]=True
                    q.append((ny,nx))
        
    return outer_air

# 그리드가 비었는지 판별합니다.
def is_empty_grid(grid):
    for row in grid:
        for block in row:
            if block==1:
                return False
    return True

# 최종 시간 계산
def cal_total_time(grid,n,m):
    dirs=[(0,1),(-1,0),(0,-1),(1,0)]
    total_time=0
    
    while True:
        if is_empty_grid(grid):
            break
        
        outer_air=bfs_outer_air(grid)
        new_grid=[row[:] for row in grid] #deepcopy
        for i in range(n):
            for j in range(m):
                if grid[i][j]==1:
                    cnt=0
                    for di,dj in dirs:
                        ni,nj=i+di,j+dj
                        if 0<=ni<n and 0<=nj<m:
                            if grid[ni][nj]==0 and outer_air[ni][nj]:
                                cnt+=1
                    if cnt>=2:
                        new_grid[i][j]=0
        total_time+=1
        grid=[row[:] for row in new_grid]
    
    return total_time

def main():
    n,m=map(int,input().split())
    grid=[list(map(int,input().split())) for _ in range(n)]
    print(cal_total_time(grid,n,m))
    
if __name__=="__main__":
    main()