[Algorithm] BaekJoon : 2638. 치즈 by Python

[문제 바로가기] https://www.acmicpc.net/problem/2638

2638번: 치즈

 

📌 문제 설명

 

N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다.

그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

<그림 1>

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

<그림 2>

<그림 3>

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

출력

출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

 

---

💡 문제 풀이

구현 + BFS 로 해결한 문제다.

 

[구현 + DFS/BFS] 유형은 주어진 문제의 내용을 순서대로 구현하면 된다.

 

모든 치즈가 녹아 없어질때까지의 시간을 계산하면 되므로, 주어진 모눈종이에 남아있는 치즈를 변수(last)에 담아둔 후

아래의 1번 ~ 2번과정을 반복한다.

 

1. 외부공기 체크 : 모눈종이의 맨 가장자리에는 치즈가 놓이지 않으므로 BFS를 이용하여 외부공기면 -1로 바꿔준다.

2. 치즈가 녹는과정 : 모눈종이를 탐색하면서 치즈인 경우, 외부공기와 접촉이 2변 이상이면 빈 공간(0)으로 바꿔준다.

   2-1. 빈 공간으로 바꿔줄 때마다(= 치즈가 녹음) 치즈의 개수를 -1 해준다.

 

남아있는 치즈가 없으면 1번 ~ 2번과정을 반복한 횟수(answer)를 출력한다.

 

 

 

코드는 다음과 같다.

import sys
from collections import deque
sys.stdin = open('백준2638. 치즈.txt', 'r')

# 외부공기 체크
def air():
    queue = deque([(0, 0)])
    visited = [[0] * M for _ in range(N)]
    visited[0][0] = -1
    while queue:
        r, c = queue.popleft()
        for i in range(4):
            nr, nc = r+d[i][0], c+d[i][1]
            if 0 <= nr < N and 0 <= nc < M:
                if not visited[nr][nc] and cheeze[nr][nc] <= 0:
                    queue.append((nr, nc))
                    visited[nr][nc] = 1
                    cheeze[nr][nc] = -1

# 치즈가 녹는 과정
def melt():
    global last
    candidates = []
    for r in range(N):
        for c in range(M):
            if cheeze[r][c] == 1:
                cnt = 0
                for i in range(4):
                    nr, nc = r+d[i][0], c+d[i][1]
                    if 0 <= nr < N and 0 <= nc < M and cheeze[nr][nc] == -1:
                        cnt += 1
                if cnt >= 2:
                    candidates.append((r, c))
    while candidates:
        r, c = candidates.pop()
        cheeze[r][c] = 0
        last -= 1

N, M = map(int, input().split())
d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
cheeze = []
last, answer = 0, 0
for _ in range(N):
    row = list(map(int, sys.stdin.readline().split()))
    last += sum(row)
    cheeze.append(row)

# 치즈가 남아있을때 까지 반복
while last:
    air()
    melt()
    answer += 1
print(answer)

---