[BOJ 2636] 치즈 (Python)

문제

치즈

---

문제 해설

이 문제는 치즈와 유사한 문제입니다. 다만 다른점은 변의 노출 개수에 영향을 받는 다는 점입니다. 문제의 요구 사항은 외부에 노출된 치즈를 녹이는 것입니다.

노출된 치즈는 외부에서부터 BFS 탐색을 이용하여 찾아낼 수 있습니다. 즉, 외부인 (0, 0) 부터 bfs를 진행하게 되면 겉에 노출된 치즈를 구할수 있다는 것입니다.

1. 처음 치즈의 개수를 셉니다.
2. (0, 0) 부터 bfs를 시작하여 치즈의 좌표를 set에 저장합니다.
3. 만약 현재 치즈의 개수와 set의 크기가 같다면 이번에 모든 치즈가 없어지므로 종료합니다.
4. 종료되지 않으면 set에 저장된 치즈의 좌표를 queue에 모두 옮기고 치즈의 개수를 갱신합니다.
5. 2 ~ 4 반복

---

풀이 코드

from collections import deque
import sys

input = sys.stdin.readline
n, m = map(int, input().split())
dx = -1, 0, 1, 0
dy = 0, 1, 0, -1
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * m for _ in range(n)]
# 처음 치즈 개수 세기
cheeze = 0
for i in range(n):
    cheeze += graph[i].count(1)

# bfs로 가장자리 탐색
q = deque([(0, 0)])
answer = 0
while cheeze != 0:
    s = set()
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 범위 안이고 아직 방문하지 않았다.
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                # 그게 치즈면 set에 저장
                if graph[nx][ny] == 1:
                    s.add((nx, ny))
                # 치즈가 아니면 큐와 visited 갱신
                else:
                    q.append((nx, ny))
                    visited[nx][ny] = True
    answer += 1
    # 종료 조건
    if cheeze - len(s) == 0:
        print(answer)
        print(len(s))
        break
    # set에는 없어질 치즈의 좌표가 들어있다.
    for x, y in s:
        cheeze -= 1
        visited[x][y] = True
        q.append((x, y))
        graph[x][y] = 0

---