[BOJ] 2638번 : 치즈(BFS, DFS etc..)

접근

치즈가 녹아내리는 문제다. 치즈 안쪽으로는 냉기가 있어서, 바깥쪽부터 녹는다는 아주 현실적인 문제.

중요한 포인트는 두가지다.

• 치즈 바깥쪽의 공기를 인식하는 것.
• 외부 공기와 접촉한 치즈만을 판단하는 것.

이 두가지만을 주의하고 문제를 해결하면 쉽게 해결이 가능하다.

해결

치즈 바깥쪽의 공기만을 인식하는 건 어떻게 하면될까? 치즈 내부의 공기를 생각해보자. 치즈 내부의 공기는 치즈로 둘러싸여있을 것이다.

예제 그림

그렇다면, 치즈인 곳은 탐색을 진행할 때 어떤 탐색(dfs, bfs)이든, 넣어주지 않게되면, 치즈 안쪽으로는 절대 탐색이 불가능하게 될 것이다. 그걸 이용해서 치즈 외부공기를 먼저 인식해주자.

 

그렇게 외부공기를 인식한다음, 그냥 이중 반복문으로 해결해도 되고, 또 효율적인 탐색법을 이용해도 좋으니 치즈의 주변 외부공기가 2개 이상이 된다면, 해당 치즈를 녹여주면 된다.

여기서도 주의점이 있는데, 치즈는 녹일 치즈들을 모은다음에 한번에 처리해주자. 안그러면, 주변부에 치즈가 녹아서 해당 부분도 공기인 곳으로 인식하게 될 수 있다.

 

그 두가지만 주의하고 처리해주면 쉽게 해결할 수 있다.

코드

from collections import deque
import sys

input = sys.stdin.readline

N, M = map(int, input().split())
graphs = [list(map(int, input().split())) for _ in range(N)]
melt_time = 0

def air_cover_cnt(y, x, N, M):
    cnt = 0
    
    dy = [0, 0, -1, 1]
    dx = [-1, 1, 0, 0]
    
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        
        if 0 <= ny < N and 0 <= nx < M and graphs[ny][nx] == -1: # 주변 외부공기 갯수 체크
            cnt += 1
            
    return cnt


while True:
    melt_time += 1
    
    que = deque([])
    dy = [0, 0, -1, 1]
    dx = [-1, 1, 0 , 0]

    visited = [[False for _ in range(M)] for _ in range(N)]
    visited[0][0] = True
    graphs[0][0] = -1
    que.append([0, 0]) # 방문 큐에 추가
    
    while que: # bfs 순회 시작
        y, x = que.popleft()

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

            if 0 <= ny < N and 0 <= nx < M: 
                if not visited[ny][nx] and (graphs[ny][nx] == 0 or graphs[ny][nx] == -1): # 범위 내에 있으면,
                    visited[ny][nx] = True
                    graphs[ny][nx] = -1 # 외부공기는 -1로 인식해준다.
                    que.append([ny, nx])
      
    cheese = []
    visited = [[False for _ in range(M)] for _ in range(N)]
    for i in range(N):
        for j in range(M):
            if graphs[i][j] == 1 and air_cover_cnt(i, j, N, M) > 1: # 치즈면서, 주변 공기가 2개 이상이면
                cheese.append([i, j])
                
    for i in cheese:
        graphs[i[0]][i[1]] = -1
        
    flag = False
    for i in range(N):
        for j in range(M):
            if graphs[i][j] == 1:
                flag = True
                
    if not flag:
        break

print(melt_time)