[백준 파이썬] #2636. 치즈

풀기 전 생각해보기😮

• 치즈가 모두 녹는 지점 파악하기

---

풀이🛫

# 구하려는 것 : 치즈가 모두 녹아 없어지는 시간, 모두 녹기 한 시간 전에 남아있는 치즈조각
# 딥카피 연습: copy_arr = [arr[i][:] for i in range(len(arr))]

from collections import deque

dcol = [1, 0, -1, 0]
drow = [0, -1, 0, 1]


# melt() 치즈의 테두리 표시
def melt():
    visited = [[0] * R for _ in range(C)]
    temp_lst = []
    queue = deque()
    queue.append((0, 0))

    while queue:
        col, row = queue.popleft()
        for v in range(4):
            ncol = col + dcol[v]
            nrow = row + drow[v]
            if 0<=ncol<C and 0<=nrow<R:
                if arr[ncol][nrow] == 0 and visited[ncol][nrow] == 0:
                    visited[ncol][nrow] = 1
                    queue.append((ncol, nrow))
                elif arr[ncol][nrow] == 1:
                    arr[ncol][nrow] = -1
                    temp_lst.append((ncol, nrow))

    for c, r in temp_lst:
        arr[c][r] = 0

    ans_lst.append(len(temp_lst))
    return len(temp_lst)


C, R = map(int, input().split())    # C: 세로, R: 가로
arr = [list(map(int, input().split())) for _ in range(C)]
idx, residue = 0, 0xfff
ans_lst = []

while melt() > 0:
    melt()

for i in range(len(ans_lst)):
    if ans_lst[i] and residue > ans_lst[i]:
        residue = ans_lst[i]
        idx = i+1

print(idx)
print(residue)

 

핵심 정리🎁

• arr의 (0, 0) 지점은 x로 표시된 판의 틀이기 때문에 치즈가 있을 수 없다는 가정을 했다
• (0, 0) 지점으로부터 탐색을 했을 때 만나는 1의 위치가 녹을 예정인 치즈의 테두리가 될 것이다.
• 치즈가 녹는 동작을 나타내는 melt() 함수를 몇번 실행시켜야 할지 고민하게 되었다.
• 남아있는 치즈의 테두리 부분의 갯수가 0이 되기 전의 지점에서 정답에 필요한 요소를 찾았다
  idx : 치즈가 녹아서 없어지는데 걸리는 시간, residue 남아있는 치즈의 양 

 

링크💎

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

2636번: 치즈

 

후기 😎

• 구현의 단계를 나누어서 함수형태로 만들어가는 풀이를 습관화 하자