[백준/알고리즘/python/java] 2636번 - 치즈

이미지를 누르면 문제 링크를 보실 수 있습니다.

이미지를 누르면 문제 링크를 보실 수 있습니다.

이미지를 누르면 문제 링크를 보실 수 있습니다.

 

문제를 먼저 해석해봅시다!

문제에서는 직사각형 모양의 판에 치즈가 표시되어 있습니다. 치즈는 1로 표시되며, 치즈가 없는 부분은 0으로 표시됩니다. 각 시간 단위마다 외부 공기와 접촉한 치즈가 녹아 없어지는데요, 이 때, 치즈의 내부에 있는 공기는 외부 공기로 간주되지 않는게 핵심입니다!

문제의 목표는 모든 치즈가 녹는 데 걸리는 시간과 마지막으로 녹기 전의 치즈 조각의 수를 찾는 것입니다.

 

이를 위해 BFS 알고리즘을 사용합니다. BFS는 주로 그래프의 최단 경로를 찾거나, 2차원 배열에서 특정 조건에 따라 요소를 탐색할 때 사용되는 알고리즘입니다. 이 문제에서는 BFS를 이용해 보드의 가장자리부터 시작하여 외부 공기를 탐색하고, 이를 통해 치즈의 녹는 경계를 식별합니다.

 

외부의 공기와 내부의 공기를 구분하고, 치즈의 녹는 경계를 식별하는게 중요합니다. 그 후, 시간이 1 지날 때마다 녹은 치즈의 영역을 카운트해주며 마지막 치즈가 다 녹기 직전에는 치즈의 영역이 몇이었는지를 구하면 되는 문제인 셈이죠.

 

해결 전략을 정리하면 아래와 같습니다.

1. 외부 공기 탐색 : 보드의 가장자리에서 BFS를 시작하여(왼쪽 상단 끝, 오른쪽 상단 끝, 왼쪽 하단 끝, 오른쪽 하단 끝 중 어디든) 외부 공기를 탐색합니다.
2. 치즈 녹이기 : 외부 공기와 접촉한 치즈를 찾아 녹입니다. 이는 BFS 탐색 중에 visited 가 False이고(아직 방문하지 않은 위치) 보드의 위치가 1로 표시된 셀을 0으로 변경하는 것으로 구현할 수 있습니다.
3. 시간 추적 : 모든 치즈가 녹을 때 까지 이 과정을 반복하고, 각 단계마다 경과 시간을 기록합니다.

해당 로직을 적용한 코드는 아래와 같습니다.

from collections import deque
import sys
input = sys.stdin.readline


def bfs():

    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]

    queue = deque([(0, 0)])
    visited = [[False] * m for _ in range(n)]
    visited[0][0] = True

    melt = 0     # 녹는 치즈의 수

    while queue:
        r, c = queue.popleft()
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            if 0<= nr < n and 0<= nc < m and not visited[nr][nc]:
                visited[nr][nc] = True
                if graph[nr][nc] == 0:   # 외부 공기
                    queue.append((nr,nc))
                elif graph[nr][nc] == 1:   # 외부 공기와 접촉한 치즈
                    graph[nr][nc] = 0   # 치즈를 녹인다.
                    melt += 1

    return melt


n, m = map(int,input().split())

graph =[]
for i in range(n):
    graph.append(list(map(int,input().strip().split())))

# 외부 공기와 내부 공기 구분하는 것이 핵심

times = 0
last_cheese = 0

while True:

    melted = bfs()

    if melted == 0:
        break

    last_cheese = melted
    times += 1

print(times)
print(last_cheese)

 

 

코드에 대한 로직은 주석으로 표시했습니다. 주목해야 할 포인트는 아래와 같습니다.

• BFS 초기 설정:
  • 'deque'를 사용하여 큐를 초기화하고, 시작점을 (0,0)으로 설정합니다. 이는 보드의 외부 공기를 나타냅니다.
  • 'visited' 배열을 사용하여 이미 방문한 셀을 표시합니다.

 

• BFS 실행:
  • 'queue'에서 좌표를 하나씩 꺼내어 상하좌우를 탐색합니다.
  • 만약 인접 셀이 치즈(1)라면, 이를 녹입니다.('graph[nr][nc] = 0') 를 하고, 'melt' 카운트를 증가시킵니다.

 

• 메인 루프:
  • 'while True' 루프를 통해 모든 치즈가 녹을 때까지 BFS를 반복합니다.
  • 각 반복마다 녹은 치즈의 수('melted') 를 확인하여, 더 이상 녹을 치즈가 없으면 루프를 종료합니다.

 

• 결과 출력:
  • 치즈가 모두 녹는데 걸리는 시간('times')과 마지막으로 녹기 전 치즈의 양('last_cheese')을 출력합니다.

 

이상으로, BFS 알고리즘을 이용하여 복잡한 조건을 가진 2차원 배열을 효과적으로 처리하는 문제인 '치즈' 문제에 대해 알아봤습니다.

여러분의 질문과 피드백을 환영합니다! 추가적인 설명이 필요하거나, 다른 방법에 대해 토론하고 싶다면 댓글을 남겨주세요!🙌