[BOJ] 치즈

2638번 치즈: 골드4

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

height, width = list(map(int, input().split()))
cheeze = []

for _ in range(height):
    cheeze.append(list(map(int, input().split())))

chz = set()
inair = set()
for i in range(height):
    for j in range(width):
        if cheeze[i][j] == 1:
            chz.add((i,j))
        else:
            inair.add((i,j))
# 내부공기 찾아주기
v = set()
v.add((0,0))
while v:
    y,x = v.pop()
    inair.remove((y,x))
    for i,j in [(y-1,x),(y+1,x),(y,x+1),(y,x-1)]:
        if (i,j) in inair:
            v.add((i,j))

def isMelting(dot):
    y,x = dot
    air = 0
    for i,j in [(y-1,x),(y+1,x),(y,x+1),(y,x-1)]:
        if (i,j) not in chz and (i,j) not in inair:
            air += 1
            if air >= 2:
                return True
    return False

def resetAir(melting):
    global inair
    d = set()
    for y,x in inair:
        for i,j in [(y-1,x),(y+1,x),(y,x+1),(y,x-1)]:
            if (i,j) in melting:
                d.add((y,x))
                break
    inair -= d
    while len(d) > 0:
        r = set()
        for y,x in d:
            for i,j in [(y-1,x),(y+1,x),(y,x+1),(y,x-1)]:
                if (i,j) in inair:
                    r.add((i,j))
        inair -= d
        d = r

time = 0
while len(chz) > 0:
    melting = set()
    for ch in chz:
        if isMelting(ch):
            melting.add(ch)
    # 내부공기 갱신
    resetAir(melting)
    chz = chz - melting
    time += 1
print(time)

---

가장 먼저 chz 와 inair set 을 만들어줬다.
inair 은 일단 공기가 존재하는 모든 좌표를 담은 후, (0,0) 에 연결된 점들을 모두 제거해줬다.

chz = set()
inair = set()
for i in range(height):
    for j in range(width):
        if cheeze[i][j] == 1:
            chz.add((i,j))
        else:
            inair.add((i,j))
# 내부공기 찾아주기
v = set()
v.add((0,0))
while v:
    y,x = v.pop()
    inair.remove((y,x))
    for i,j in [(y-1,x),(y+1,x),(y,x+1),(y,x-1)]:
        if (i,j) in inair:
            v.add((i,j))

---

isMelting(dot) : dot 에 있는 치즈가 현재 녹는 상황(4면 중 2면 이상이 외부 공기에 노출)에 있는 지 return 한다.
resetAir() : 새로운 melting(녹은 치즈의 배열)을 참고하여 내부공기inair set을 갱신시켜준다. (만약 inair의 상하좌우에 있던 치즈가 녹았다면 그 inair 는 외부 공기에 노출 -> 그와 연결된 모든 inair 를 제거)

---

time = 0
while len(chz) > 0:
    melting = set()
    for ch in chz:
        if isMelting(ch):
            melting.add(ch)
    # 내부공기 갱신
    resetAir(melting)
    chz = chz - melting
    time += 1
print(time)

chz 에 있는 모든 치즈 원소들에 대하여 isMelting으로 녹을 예정인 지 확인한다. 녹을 치즈의 배열을 이용하여 내부 공기를 갱신하고, chz 에서 녹은 치즈를 빼주고 시간을 하나 증가시켜준다. 위 과정을 chz 의 치즈 원소들이 모두 사라질때까지 반복한다.

---