[BOJ] 2636. 치즈 / BFS / Python 풀이

 

2636번: 치즈

 

오랜만에 포스팅, 최근 풀고 있는 BFS 문제다.

백준 2636번 문제로 골드4인데 정답률은 50퍼센트를 넘는다..

친구와 함께 풀다가 몇 가지 힌트를 얻고 한 번에 통과했다 ㅎㅎ

 

 

문제 이해

 

출처: 백준

공기와 접촉된 칸은 한 시간이 되면 녹아 없어진다.

이때 치즈로 둘러싸인 구멍은 공기와 접촉된 것으로 치지 않는다.

이 부분의 설명이 이해하기 쉽지 않아서 주춤했다.

 

접근

 

문제를 보자마자 너비 우선 탐색으로 접근했고,

처음에는 공기와 닿은 치즈를 어떻게 알아낼지가 고민이었다.

문제 설명에서 가장자리에는 치즈가 들어가지 않는 게 힌트가 되었다.

공기의 주변을 탐색해 녹을 치즈를 알아내면 되겠다고 생각했다.

큐를 두 개 사용해 공기를 넣을 큐, 치즈를 넣을 큐를 따로 만들기로 했다.

 

풀이

 

두 개의 큐는 queue와 cheese로 만들어주었다.

queue에는 공기가 들어가 주변을 탐색하고

cheese에는 공기와 맞닿아 있는 가장자리 치즈가 들어간다.

한 번 탐색된 곳은 -1로 방문 처리 해주었다.

그 이후로는 queue에 cheese를 복사하여 공기의 역할을 하고, 다음에 녹을 치즈를 cheese에 넣어준다.

공기 통해 가장 자리를 탐색하는 데에 loop 한 번을 돌기 때문에 ans는 -1로 초기화했다.

 

파이썬 코드는 다음과 같다.

from collections import deque

def bfs():
    queue = deque()
    cheese = deque()
    ans = -1
    piece = 0
    
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    
    queue.append([0, 0])
    matrix[0][0] = -1
    
    while True:
        while queue:
            a, b = queue.popleft()
            
            for i in range(4):
                x = dx[i] + a
                y = dy[i] + b
                
                if 0 <= x < col and 0 <= y < raw:
                    if matrix[y][x] == 0:
                        queue.append([x, y])
                    elif matrix[y][x] == 1:
                        cheese.append([x, y])
                    matrix[y][x] = -1
        ans += 1
        
        if cheese:
            piece = len(cheese)
            queue = cheese
            cheese = deque()
        else:
            return(f'{ans}\n{piece}')

raw, col = map(int, input().split())

matrix = ['']*raw
for i in range(raw):
    matrix[i] = list(map(int, input().split()))

print(bfs())

 

후기

 

이제 BFS에는 많이 익숙해진 것 같다.

지금까지 풀었던 문제들도 정리하고 다른 유형으로 넘어가야겠다!