2636. 치즈

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

2636번: 치즈

Solution

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

def melt():
    num = 0
    while(ready):
        i, j = ready.pop()
        cheese[i][j] = 0
        num += 1
    return num

def chk():
    while(q):
        i, j = q.pop()
        
        if cheese[i][j] == 1:
            ready.append((i,j))
            continue
        
        for d in delta:
            dr, dc = i+d[0], j+d[1]
            if (0 <= dr < row) and (0 <= dc < col) and not visited[dr][dc]:
                q.append((dr, dc))
                visited[dr][dc] = True
    return melt()    

row, col = map(int, input().split())
cheese = []
for _ in range(row):
    cheese.append(list(map(int, input().split())))

delta = [[-1, 0], [1, 0], [0, -1], [0, 1]]
now, pre = 10000, 10000
q = deque()
ready = deque()
time = -1

while(now):
    visited = [[False]*col for _ in range(row)]
    q.append((0,0))
    pre = now
    now = chk()
    time += 1

print(time)
print(pre)

• 입력을 받고 필요한 변수를 선언한다.
  • now : 방금 chk( ) 함수를 통해서 녹은 치즈의 개수. 이게 0이 되면 pre가 정답이다.
  • pre : 이전 now 값
  • q : 녹을 치즈인지 확인하는 좌표가 들어간다.
  • ready : 녹을 치즈를 찾았을 때, 나중에 반영하기 위해 그 좌표를 넣는다.
  • time : 몇 번 chk( )를 돌았는지 count
• 녹은 치즈가 하나도 없을 때까지 while을 반복한다.
• visited를 초기화한다.
• q에 시작좌표를 넣고 now를 pre에 백업한다.
• chk( ) 실행하여 몇 개의 치즈가 녹았는 지 저장한다.
  • 큐에서 좌표를 뽑고 1이면 치즈이므로 ready에 넣고 탐색은 멈춘다.
  • 치즈가 아니면 4방향으로 탐색한다.
  • 범위를 넘지 않고 방문하지 않았다면 큐에 넣고 visited에 표시한다.
  • 큐가 비어 있게 되면 모든 검사를 한 것이므로 mel( ) 를 수행
    • ready에서 좌표를 꺼내면서 실제 cheese가 녹은 곳을 적용한다.
    • 녹은 치즈의 개수를 반환한다.

Another

n, m = map(int, input().split())
board = [list(map(int, input().split())) for i in range(n)]

visit = [[False]*m for i in range(n)]
stack = [(0, 0)]
cnt = 0
meltnum = 0
while True:
    melt = []
    while stack:
        y, x = stack.pop()
        for i,j in [(1,0),(-1,0),(0,1),(0,-1)]:
            dy, dx = y+i, x+j
            if 0<=dy<n and 0<=dx<m and not visit[dy][dx]:
                if board[dy][dx]==0 :
                    stack.append((dy, dx))
                else :
                    melt.append((dy, dx))
                visit[dy][dx] = True
    if melt:
        meltnum = len(melt)
    else :
        break
    stack.extend(melt)
    cnt+=1
print(cnt)
print(meltnum)

• 비슷하지만 조금 다르고 효율적이다.
• 입력으로 받은 board를 바꾸지 않고 visit만을 이용한다.
• 스택에 있는 것을 빼면서 그 좌표가 범위에 들어있고, 방문한 곳이 아닌지 확인한다.
  • 조건을 만족하고 이게 치즈가 아니라면 스택에 넣고, 치즈라면 melt에 넣는다.
  • 방문한 곳을 체크한다.
• 스택이 비어있으면 나오게 되고 melt의 길이로 녹은 치즈의 개수를 센다.
• 그리고 melt에 있는 것을 스택에 넣어서 다음 후보로 사용한다.
• 어차피 이전에 방문한 곳은 보지 않아도 되고, 치즈의 위치라도 방문한 곳은 안가므로 board를 수정할 필요가 없다.
• 그렇게 melt가 비어있을 땐 더이상 녹을 치즈가 없다는 것이므로 마무리한다.