치즈

풀이

 처음에는 bfs의 시작 위치를 치즈로 잡았다. 치즈의 주변(상,하,좌,우)을 탐색하면서 공기가 있으면 치즈를 녹이는 식으로 생각했지만 이럴 경우에 치즈 내부 구멍 가장자리도 녹아버리는 문제가 발생한다. 따라서 공기인 (0,0)에서 bfs를 진행하는 식으로 아이디어를 바꿨다. 간단하게 플로우를 설명하자면 (0,0) 에서 bfs를 시작해서 값이 0이면 queue에 넣고 방문 처리, 값이 1이면 값을 0로 수정하고 방문처리하면 된다. 아래 while 문이 몇 번 돌아가는지 count 값을 출력하면 정답이다.

while(graph의 모든 원소가 !=0)

• visited 초기화
• (0,0) 에서 bfs 수행
  • if 값 == 0 -> queue에 삽입, visited 기록
  • elif 값 == 1 -> 값을 0으로 수정, visited 기록

시간복잡도는 O(time*n^2)인데 time은 최악의 경우 max(a, b)이기 때문에 대략 O(n^3) 정도인 거 같다.

from collections import deque
import sys

a, b = map(int, input().split())
graph = []
for i in range(a):
    graph.append(list(map(int, sys.stdin.readline().split())))

# 동, 서, 남, 북
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs():
    count = 0
    queue = deque([(0,0)])
    while(queue):
        x,y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<a and 0<=ny<b:
                if graph[nx][ny] == 0 and visited[nx][ny] == False:
                    visited[nx][ny] = True
                    queue.append((nx,ny))
                if graph[nx][ny] == 1 and visited[nx][ny] == False:
                    graph[nx][ny] = 0
                    visited[nx][ny] = True
                    count += 1
    return count

result = 0
data = []
while(True):
    visited = [[False] * b for _ in range(a)]
    count = bfs()
    data.append(count)
    if count == 0:
        break
    result += 1
print(result)
print(data[-2])

시간복잡도 : O(n^3)