[BOJ][Python]2638 풀이

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

2638번: 치즈

from collections import deque
import sys
ssr = sys.stdin.readline

def outer_air():
    nomis = []
    while q:
        r, c = q.popleft()
        for dr, dc in dpos:
            if 0 <= r+dr < n and 0 <= c+dc < m and visited[r+dr][c+dc] == False:
                if board[r+dr][c+dc] == 0:
                    q.append((r+dr, c+dc))
                    nomis.append((r+dr, c+dc))
                    visited[r+dr][c+dc] = True
                elif board[r+dr][c+dc] == 1:
                    cheese.add((r+dr, c+dc))
    for r, c in nomis:
        board[r][c] = 2
                        
def melt_cheese():
    nomis = []
    while len(cheese) > 0:
        r, c = cheese.pop()
        cnt = 0
        for dr, dc in dpos:
            if board[r+dr][c+dc] == 2:
                cnt += 1
        if cnt > 1:
            nomis.append((r, c))
            q.append((r, c))
    for r, c in nomis:
        board[r][c] = 2

n, m = map(int, ssr().split())
board = [list(map(int, ssr().split())) for _ in range(n)]
visited = [[False for _ in range(m)] for _ in range(n)]
dpos = [(1, 0), (-1, 0), (0, 1), (0, -1)]
q = deque([(0, 0)])
board[0][0] = 2
cheese = set([])
ans = 0
while True:
    outer_air()
    if len(cheese) == 0:
        print(ans)
        break
    else:
        melt_cheese()
        ans += 1

늘 하던 그래프 탐색 문제입니다만 약간 주의해야 할 점은 조건에 맞는다고 값을 바로 바꾸면 안된다는 점일까요. 예를 들어 치즈가 완전한 3*3 사이즈 정사각형이고 빈공간이 없다고 해보겠습니다. 시작 위치는 임시로 치즈의 왼쪽 위 꼭짓점이라고 해볼게요.

0 0 0 0 0

0 1 1 1 0

0 1 1 1 0

0 1 1 1 0

0 0 0 0 0

이런 형태로 (1, 1) 의 좌표에서 시작을 하게 되겠네요. 이 때 원래대로라면 4개의 꼭짓점의 치즈만 녹습니다. 하지만 그래프 탐색을 하면서 조건에 맞는다고 바로바로 값을 바꿔나가면 실제로 2개 이상의 변이 외부에 닿는 치즈가 아님에도 불구하고 방금 옆에 붙어있던 치즈가 값이 바뀌면서 공기로 취급되어 조건에 맞는 경우가 생기죠. 그래서 가운데에 있는 한칸을 남겨두고 전부 다 녹는다는 잘못된 결과가 나오게 됩니다. 그래서 저는 좌표를 따로 저장해뒀다가 함수가 끝날 때 일괄적으로 값을 바꾸는 방법을 사용했어요. 이 부분만 주의하면 딱히 어렵지는 않은 문제입니다.

 

대충 계산해봤는데 1초니까 c언어 기준 10억회의 연산이 가능하다고 치고(이 부분은 1억회다, 10억회다 얘기가 좀 분분한 것 같습니다만 당연히 실행환경에 따라 다를 수 있으니 자신있다 싶으면 좀 넉넉하게 생각하시고 괜히 시간초과를 내기 싫다면 좀 더 보수적으로 잡는 것도 괜찮습니다) 100*100이 최대 입력이니까 매 번 모든 원소에 대해 4방향을 탐색한다고 치면 25000번 이터레이션이 가능하니까 경우에 따라 다르겠지만 아마 충분히 통과될 것 같은데요. 저는 그냥 외부 공기 탐색하면서 치즈위치를 따로 저장해뒀다가 녹는 치즈 구분할 때 저장해둔 좌표만 사용하고, 녹는 치즈를 구분할 때 치즈 벽이 허물어지면서 치즈 속에 있던 공기도 외부공기가 되니까 그 때의 좌표를 따로 저장했다가 다음 번 외부 공기 이터레이션에서 사용하는 방식으로 연산량을 좀 줄여봤습니다.