[BOJ 2638] 치즈(python)

문제

치즈

---

문제 해설

BFS 또는 DFS를 활용하는 문제입니다. 치즈로 부터 BFS,DFS를 시작하면 답이 안나오고, 가장자리에는 반드시 치즈가 비어있다는 것을 이용해 가장자리 부터 탐색을 활용하는 것이 핵심입니다. 이렇게하면 치즈 내부의 공간을 체크하지 않습니다.

1. 가장자리에서 4방향 탐색을 시작한다.
2. 치즈가 발견되면 +1을 하여 외부의 접촉을 체크한다.
3. 맵중 3이상(원래치즈 1, 접촉 2이상)인 값이 발견되면 0으로 만든다.

---

풀이 코드

import sys
import copy
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
graph = []
cheeze = 0
answer = 0

for _ in range(n):
    graph.append(list(map(int, input().rstrip().split())))

# 치즈 개수 세기
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            cheeze += 1


def search(arr):
    q = deque()
    global cheeze, answer, n, m
    visited = [[False] * m for _ in range(n)]
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    q.append((0, 0))
    visited[0][0] = True
    # 바깥에서부터 4방 탐색 시작
    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:
                if arr[nx][ny] >= 1:  # 치즈가 있으면 +1
                    arr[nx][ny] += 1
                if not visited[nx][ny] and arr[nx][ny] == 0:
                    visited[nx][ny] = True
                    q.append((nx, ny))
    for i in range(n):
        for j in range(m):
            if arr[i][j] >= 3:
                graph[i][j] = 0
                cheeze -= 1
    answer += 1


while cheeze != 0:
    search(copy.deepcopy(graph))
print(answer)