[BOJ][Python] 2638번 치즈

1. 문제

https://www.acmicpc.net/problem/2638

2638번: 치즈

---

2. 문제 풀이 알고리즘

N x M 칸에 치즈가 놓여있는데, 1이 치즈, 0이 공기를 나타낸다. 치즈 한 칸은 상하좌우 중 공기와 닿는 부분이 2칸 이상 있으면 녹게 된다. 치즈가 모두 녹았을 때의 시간을 구해야 하는 문제이다.

빙산이 녹을 때를 구하는 문제와 차이점은 치즈의 내부 공기는 치즈를 녹는 데에 영향을 줄 수 없다는 것이다. 따라서 치즈의 내부 공기와 외부 공기를 구분해주어야 한다.

 

---

3. 구현

1) 입력 받고 저장

import sys

n, m = map(int, sys.stdin.readline().strip().split())
area = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

cheese = []
for i in range(n):
    for j in range(m):
        if area[i][j] == 1:
            cheese.append([i, j])

• cheese (list): 치즈의 좌표를 모두 담은 리스트, 처음 실행할 때는 입력 받은 값 중 1의 좌표를 모두 넣어주었고, 한 시간이 지날 때마다 next_hour()이 실행되면서 공기가 된 치즈를 제외한 좌표들로 계속 업데이트 된다.

2) 함수구현

def div_area(q):
    while q:
        r, c = q.popleft()

        for x, y in [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]:
            if 0<= x < n and 0<= y < m:
                if area[x][y] == 0:
                    area[x][y] = -1
                    q.append([x, y])

• div_area(q)
  • q는 외부 공기의 좌표 중 일부를 담은 덱이다. 이 함수에서는 q에 상하좌우로 연결될 공기(0)를 bfs로 탐색하여 -1로 만든다. 즉, 외부 공기와 내부공기를 구분하기 위해 외부 공기는 -1, 내부 공기는 0으로 표시하는 것이다.
  • 처음 시작할 때는 판의 테두리는 모두 공기라는 것을 이용하기 위해 q에 (0,0) 하나를 넣어 외부공기를 -1로 셋팅하였다.
  • 한 시간이 지날 때마다 치즈가 녹음에 따라 외부공기와 내부공기가 연결될 수 있는데, 이 때 녹은 치즈의 좌표를 모두 덱(new_air)에 넣어 이 함수를 호출하여 외부공기를 업데이트 해주었다.

def next_hour():
    global cheese
    new_cheese = []
    new_air = deque()

    for i, j in cheese:
        cnt = 0

        for x, y in [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]]:
            if area[x][y] == -1:
                cnt += 1
        if cnt >= 2:
            new_air.append([i, j])
        else:
            new_cheese.append([i, j])
    
    for i, j in new_air:
        area[i][j] = -1

    div_area(new_air)
    cheese = new_cheese

• next_hour() 
  • 치즈의 좌표들을 cheese 리스트에서 꺼내 하나 씩 탐색하며 2면 이상에 외부 공기가(area의 값이 -1) 있는 것은 녹게되는 치즈이므로 new_air에, 그렇지 않을 때는 new_cheese에 넣어주고 new_air는 모두 -1로 초기화해주었다. 그리고 외부 공기와 내부 공기가 연결된 것을 다시 찾기 위해 div_area를 호출해주었다. 

3) 전체 코드

import sys
from collections import deque

def div_area(q):
    while q:
        r, c = q.popleft()

        for x, y in [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]:
            if 0<= x < n and 0<= y < m:
                if area[x][y] == 0:
                    area[x][y] = -1
                    q.append([x, y])

def next_hour():
    global cheese
    new_cheese = []
    new_air = deque()

    for i, j in cheese:
        cnt = 0

        for x, y in [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]]:
            if area[x][y] == -1:
                cnt += 1
        if cnt >= 2:
            new_air.append([i, j])
        else:
            new_cheese.append([i, j])
    
    for i, j in new_air:
        area[i][j] = -1

    div_area(new_air)
    cheese = new_cheese

n, m = map(int, sys.stdin.readline().strip().split())
area = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

cheese = []
for i in range(n):
    for j in range(m):
        if area[i][j] == 1:
            cheese.append([i, j])

area[0][0] = -1
div_area(deque([[0, 0]]))

cnt = 0
while cheese:
    next_hour()
    cnt += 1

print(cnt)

while cheese로 치즈가 없어질 때까지 next_hour을 호출하며 cnt의 값을 하나씩 늘려주고, 마지막에 cnt의 값을 출력해주었다.