Python으로 푸는 백준 2638. 치즈

이 문제는 실온에 둔 치즈가 있고,

공기를 접한 치즈 부분은 정확히 한시간 후에 사라진다고 가정했을 때,

치즈의 모든 부분이 녹아 없어지는게 걸리는 정확한 시간을 구하는 프로그램을 작성해야 한다.

백준에서 푼 문제 리스트 보기

백준에서 문제 보기

github에서 코드 보기

문제 풀이

공기에 닿은 치즈인지를 구분하는 방법을 찾는게 문제 풀이의 관건이다. 공기와 밀접한 치즈의 경우에는 얼마나 많은 면이 공기와 맞닿아 있는지 치즈에 수치를 적어준다. 수치가 2이상인 치즈와 맞닿아 있는 치즈인 경우에는 직접적으로 공기와 닿진 않지만 간접적으로 공기와 닿아있는 것과 같다. 치즈를 다 녹인 다음에는 다시 수치를 측정하기 위해서 치즈의 수치를 본래 값으로 변경해주어야 한다.

파이썬 코드

import sys
import copy
 
direction = [(0,1),(1,0),(0,-1),(-1,0)]
 
def solve(n, m, array):
    time = 0
    while True:
        checkCheese(n, m, array)
        extraCount = meltDown(n, m, array)
        time += 1
        if extraCount == 0:
            array = None
            return time
 
def checkCheese(n, m, array): 
    queue = []
    queue.append((0,0))
    while queue:
        pos = queue.pop(0)
        i = pos[0]
        j = pos[1]
        if array[i][j] == 0:
            array[i][j] = -1
            for case in direction:
                next_i = i + case[0]
                next_j = j + case[1]
                if next_i > -1 and next_j > -1 and next_i < n and next_j < m:
                    next_value = array[next_i][next_j]
                    if next_value > 0:
                        array[next_i][next_j] += 1
                    elif next_value == 0:
                        queue.append((next_i, next_j))
 
def meltDown(n, m, array):
    extraCheeseCount = 0
    for i in range(n):
        for j in range(m):
            current_value = array[i][j]
            # 남은 치즈의 수
            if current_value == 1 or current_value == 2:
                extraCheeseCount += 1
                array[i][j] = 1
            # 공기와 2 이상 밀접한 치즈를 녹이거나 공기를 -1 => 0으로 바꿔준다
            if current_value == -1 or current_value > 2:
                array[i][j] = 0
    return extraCheeseCount
 
if __name__ == "__main__":
    
    n, m = sys.stdin.readline().strip().split()
    array = []
    for i in range(int(n)):
        line = list(map(int,sys.stdin.readline().strip().split()))
        array.append(line)
    print(solve(int(n), int(m), array))