[백준] 2636 치즈 python

https://acmicpc.net/problem/2636 

2636번: 치즈

from collections import deque
def bfs(q):
    melting = 0
    melt_list = set()
    while q:
        x, y = q.popleft()
        for i in range(4):
            dx = x + delta[i][0]
            dy = y + delta[i][1]
            if dx < 0 or dx >= h + 2 or dy <0 or dy >= w + 2: continue
            if visited[dx][dy]: continue
            if matrix[dx][dy]==0:
                q.append((dx, dy))
                visited[dx][dy] = 1
            else:
                melt_list.add((dx, dy))

    return melt_list

h, w = map(int, input().split())
matrix = []
for i in range(h + 2):
    if i ==0 or i == h+1:
        matrix.append([0] * (w + 2))
    else:
        tmp = list(map(int, input().split()))
        matrix.append([0] + tmp + [0])
visited = [[0] * (w + 2) for _ in range(h + 2)]
q = deque()
# print(*matrix, sep='\n', end='\n\n')
# print(*visited, sep='\n', end='\n\n')
delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]
result_time, result_cheese = -1, 0
old = 0

q.append((0, 0))
visited[0][0] = 1
while q:
    melt = bfs(q)
    result_time += 1
    result_cheese = old
    q.extend(melt)
    old = len(melt)
    while melt:
        x,y = melt.pop()
        matrix[x][y] = 0


print(result_time, result_cheese)

오랜만에 풀어본 bfs 문제이다 (오랜만은 아닌가?)

치즈의 겉면을 어떻게 파악하느냐가 주요 포인트인데 총 두가지 방법이 있다.

첫번째는 치즈 내부를 돌아다니면서 겉면인 부분을 파악하는 방법이다.

해당 풀이로는 이문제의 맹점이 있는데 공기와 접촉되지 않은 안쪽의 구멍또한 겉면으로 인식하게된다.

두번째는 공기를 돌아다니면서 겉에 닿은 치즈를 파악하는 방법이다.

나는 이 방법을 사용해서 풀었다.

모든 면이 치즈로 꽉 차있는 경우에는 공기 부분을 찾을수 없을수도 있어서

혹시나하는 마음에 입력 받을때 겉면을 0으로 감싸주었다.

bfs 내부의 알고리즘은 일반적인 bfs와 크게 다른점은 없는데 조금씩 조건들이 추가되었다.

우선 0으로 감싸주었으므로 범위가 2씩 증가하였다.

그다음은 공기만 탐색해야하므로 bfs 큐에 넣었고, 공기에 닿은 치즈는 중복될수있기 때문에 set을 만들어서 리턴해주었다.

공기에 닿은 치즈 리스트는 bfs 함수 외부에서 쓰이게 된다.

공기에 닿은 치즈들은 다음 단계에서는 공기로 변하기때문에 해당부분들을 확인할수 있게 큐에 넣어주었다.

bfs에서 큐의 전체원소를 확인해야하므로 bfs 내부에서 사용하는 큐와 전역으로 사용하는 큐는 같은 것을 사용하였다.

그리고 치즈 리스트의 갯수로 녹은 치즈가 몇개인지 알수 있어서 마지막 녹은 치즈의 갯수를 알수 있다.

마지막으로 치즈 리스트가 빌때까지 반복문을 돌려 해당 치즈의 위치를 공기(0)로 바꿔주어 다음 while문에서 돌수있게 하였다.

---

오늘은 공부하기 싫어서 하나만 풀거같은데 그래도 재밌게 풀었다.