[백준(파이썬/Python)] 2638_치즈

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

2638번: 치즈

 

이 문제의 핵심은 내부 치즈인가 아닌가를 어떤 방식으로 판단할 것인가입니다.

 

처음 문제에 접근했을 때는"모든 지점에 대하여 내부 치즈인가를 BFS 탐색을 하였고, 만약 가장자리에 도착할 수 있으면 내부 치즈가 아니다"라고 생각했습니다.

 

하지만 그렇게 되면 모든 위치마다 일일이 체크를 해줘야 하기 때문에, 시간복잡도에서 불리할 수밖에 없습니다.

 

이를 해결하기 위해서는 반대로 "가장 자리(0,0)에서 출발하여 도착할 수 있는 모든 지점은 내부 치즈가 아니다"라고 접근해야 합니다. 치즈를 지우기 전에 (0,)에서 DFS를 한 번만 수행해주면, 각 위치에 있는 치즈가 내부 치즈인지 아닌지를 한 번에 확인할 수 있습니다. 

 

그리고 치즈를 삭제할 때는 단순하게 상하좌우를 살펴서 외부 공기가 2개 이상이면 지워주는 방식으로 하면 됩니다.

 

[풀이]

import sys
from collections import deque


def checkOutsizeCheeze(i,j):
    visited = [[False] * m for _ in range(n)]
    visited[i][j] = True
    cheeze[i][j] = 2
    q = deque()
    q.append((i,j))

    while q:
        x, y = q.popleft()
        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and cheeze[nx][ny] != 1:
                visited[nx][ny] = True
                cheeze[nx][ny] = 2
                q.append((nx,ny))
    return False

def deleteCheeze():
    n, m = len(cheeze), len(cheeze[0])
    visited = [[False] * m for _ in range(n)]
    delete_list = []

    for i in range(1, n-1):
        for j in range(1, m-1):
            visited[i][j] = True
            count = 0
            for k in range(4):
                ni, nj = i + dx[k], j + dy [k]
                if cheeze[ni][nj] == 2:
                    count += 1
                    if count == 2:
                        delete_list.append((i,j))
                        break

    for x, y in delete_list:
        cheeze[x][y] = 0

n, m = map(int, input().split())
cheeze = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dx, dy = [1,-1,0,0], [0,0,1,-1]
time = 0
while True:
    # 맨 바깥쪽 공기에서 dfs로 연결된 모든 치즈는 외부 치즈다.
    checkOutsizeCheeze(0,0)

    # 치즈 삭제
    deleteCheeze()
    time += 1
    
    # 모든 치즈가 녹았는지 확인
    cheezeCount = 0
    for i in range(n):
        for j in range(m):
            if cheeze[i][j] == 1:
                cheezeCount+= 1
    if cheezeCount == 0:
        break


print(time)