. 누가 내 치즈를 옮겼을까? (백준 2638: 치즈)
본문 바로가기
프로그래밍 공부/백뚠

누가 내 치즈를 옮겼을까? (백준 2638: 치즈)

by 불냥이_ 2020. 12. 30.

2638번: 치즈 (acmicpc.net)

 

2638번: 치즈

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표

www.acmicpc.net

 

우리가 흔히들 떠올리는 치즈

 

 톰과 제리같은 만화를 보면 항상 치즈는 샛노란 색깔에 치즈케이크같은 모양에 구멍이 송송 뚫려있는 모양으로 나왔다.

그걸 보고있으면 참 맛있어 보였는데, 우리가 흔히 먹는 치즈는 네모나고 얇은 치즈였다.

 

한번은 위 사진같은 치즈를 먹은 적이 있었는데....

 

솔직히 맛은 기억 안난다. 그냥 평범했나보다. 

푸른곰팡이 치즈였나 그거는 먹은 적이 있었는데, 겉보기로 음식을 판단하는 나이기 때문에 한입먹는 것이 되게 힘들었지만 의외로 맛있었던 기억이 난다. (와인과 궁합이 좋았다.)

 

그래도 냄새때문에 많이는 못먹었지만

 

 

 

 

그래서 누가 내 치즈를 가져갔냐고

그래서 이번 시간에는 사라져버리는 치즈에 대해 다룰 것인데, 어느 쥐새끼같은 놈이 치즈를 가져갔는가 알아보자.

문제는 다음과 같다.

 

 

아하! 

치즈를 누가 가져간 것이 아니라 녹아버린 것이구나!

미안해 제리야. 의심해서.

 

안타까운 일이다. 누가 가져간 것이라면 그래도 치즈는 누군가의 뱃 속에서 행복했을건데, 그냥 사라져버리는 것은 치즈한테도 슬픈 일일 것이다. 

 

우리는 치즈가 다 녹아버리기 전에 얼마나 시간이 지나면 치즈가 다 녹아버리는 지 계산해서 얼른 먹어치우던가 나눠주던가 해야될 것이다.

 

그럼 이제 시간을 계산해보자.

 

치즈가 외부 공기와 닿으면 녹아버린다고 한다.

문제를 보면 빙산 (2573번: 빙산 (acmicpc.net)) 과 비슷할 수 있는데, 이 문제는 치즈에 둘러쌓인 공기는 외부 공기로 취급안해줘서 치즈가 녹는 것에 영향을 끼치지 못한다는 것이 다르다.

 

 

그렇다면 우리는 외부 공기만 계산해 줄 필요가 있다.

문제를 잘 읽어보면, 네 귀퉁이는 무조건 외부공기이다. 그렇다면 여기서부터 0을 탐색하여 접촉하는 0은 모두 외부공기라는 뜻이 될 것이다.

 

 

그럼, 네 귀퉁이에서 0을 탐색하는 코드를 구현해보자.

import sys
from collections import deque 

N, M = map(int,sys.stdin.readline().split())
cheeze = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
stack = [[0,0], [N-1,0], [0,M-1], [N-1,M-1]]

while stack:
    temp = stack.pop()
    x = temp[0]
    y = temp[1]
    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        if 0 <= nx < N and 0 <= ny < M:
            if cheeze[nx][ny] == 0:
                cheeze[nx][ny] = -1
                stack.append([nx,ny])

스택을 사용하여 DFS를 썼다. 이로서 시작할 때, 시작할 때, 외부공기는 모두 -1이 될 것이다.

 

시작할 때, 외부공기를 모두 -1로 바꿔주었다.

 

 

이제 치즈를 녹여줄 시간이다. 

처음에는 맵을 만들 때, 값이 1인 좌표를 전부 deque에 저장해서 거기서 사방(四方)탐색을 실시해 0이 2개 이상이면 녹이는 식으로 했었으나 시간초과가 떠 버렸다. (빙산했을 땐 됐었는데 ㅠ.ㅠ)

 

아마 처음에 외부공기를 탐색하는 시간이 압박이 되나보다. 

 

그렇다면 외부공기를 탐색하면서 치즈에 접촉하면 stack에 저장하는 식은 어떨까?

 

 

 

 

.... 그것도 역시 시간초과였다.

눈물과 고난의 기록

뭐가 문제인가 봤더니, 외부 공기 한칸에 접촉하는 친구는 괜찮았지만, 외부 공기 두 칸에 접촉하는 친구는 deque에 두번 들어가는 것이 문제였다. 

 

게다가 내 방식은 치즈가 녹고나서 그 시간 대에 다른 치즈에 영향을 끼치는 것을 방지하기 위해서, 외부 공기 두칸 접촉하는 치즈를 또 다른 deque에 저장하고 그 deque에 들어있는 치즈를 녹이는 방식이기 때문에 stack에 2배로 쌓인다면 실제 부하는 4배가 될 것이다. 

 

아마 이 문제때문에 시간초과가 떴었을 것이다. 

 

 

그러고보니 치즈가 외부공기 2칸에 접촉하든, 3칸에 접촉하든 어차피 2칸 이상이면 녹는다.

이것을 활용할 순 없을까?

 

while stack:
    temp = stack.pop()
    x = temp[0]
    y = temp[1]
    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        if 0 <= nx < N and 0 <= ny < M:
            if cheeze[nx][ny] == 0:
                cheeze[nx][ny] = -1
                stack.append([nx,ny])
            elif cheeze[nx][ny] > 0:
                cheeze[nx][ny] += 1

맨 처음에 외부공기를 탐색하기 위해서 0인 좌표에서 사방탐색을 했던 것을 기억하고 있을 것이다.

이 때, 탐색한 좌표의 값이 0보다 높다면 +1 을 해주었다. 

 

기본 치즈의 값은 1이므로, 만약 외부 공기 한 칸과 접촉하고 있다면 2, 두 칸과 접촉하고 있다면 3, 세 칸과 접촉하고 있다면 값은 4가 될 것이다. 

 

그렇다면 치즈의 값이 3이상이면 제거하면 될 것이다. 

이 과정은 간단하기 때문에 딱히 deque에 저장하지 않고 2중 for문으로 값이 3이상인 것만 제거해도 시간이 그리 오래 걸리지 않을 것이다. 

 

이를 코드로 구현해보자.

 

while True:
    cnt = 0
    for n in range(N):
        for m in range(M):
            if cheeze[n][m] > 2:
                melting.append([n,m])

    for i in range(len(melting)):
        temp = melting.pop()
        n = temp[0]
        m = temp[1]
        cnt += 1
        cheeze[n][m] = -1

    if cnt == 0:
        print(hour)
        exit()

    hour += 1

 

" 왜 이중 for문을 돌렸을 때, 2보다 높은 숫자이면 그 자리에서 안녹이고 따로 list에 빼서 지우나요? " 라고 할 수 있을 것이다.

 

그 이유는 다음과 같다.

 

치즈가 사라지면 그 자리에 외부 공기가 들어오기 때문에 주위 치즈에 +1 을 해주어야 하는데, 이중 for문이면 상기한 문제로 다음 치즈에 영향을 끼칠 수 있기 때문이다.

 

 

그런데 잠깐.

치즈가 사라지면 그 자리에 외부 공기가 들어오고, 사방탐색을 한 뒤, 치즈가 있다면 +1을 해주어야한다.

그런데 치즈가 아니라 내부 공기 (0) 이 있다면?

 

이런 경우 ( 원래는 네 귀퉁이는 외부공기이지만, 상황 이해를 돕기위해 위와 같이 했다. )

 

그렇다면 +1이 아니라 -1로 만들어줘야 하는데, 내부 공기가 이어져있을 것이다. 

그러면 DFS를 실행해서 이어진 0들을 DFS탐색을 해주어야한다.

 

근데 문제는 DFS를 탐색하고 나서, 0인 자리가 -1이 되면 또 -1과 붙어있는 치즈에 +1를 해주어야한다는 것이다.

여간 귀찮은 일이 아니다.

 

 

그런데 0의 주위값을 탐색해서 또 0이 있다면 -1로 바꿔주고, 치즈가 있다면 +1 해주는 것.

 

이전 그림에서 3이 녹는다면 이렇게 바뀌어야 할 것이다.

 

어디서 많이 본 상황이지 않은가?

그러고보니 우리는 맨 처음에 사방탐색을 실시해서 0이면 -1로 바꿔주는 코드를 만든 적이 있다.

 

바로 이 친구

while stack:
    temp = stack.pop()
    x = temp[0]
    y = temp[1]
    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        if 0 <= nx < N and 0 <= ny < M:
            if cheeze[nx][ny] == 0:
                cheeze[nx][ny] = -1
                stack.append([nx,ny])
            elif cheeze[nx][ny] > 0:
                cheeze[nx][ny] += 1

 

이 친구를 함수화하여서, 녹은 치즈 자리 주위에 내부 공기(0)이 있다면, 0을 찾아다니면서 -1로 바꿔주고, 또 그 -1과 접촉한 치즈에 +1 를 해주는 코드를 구현해보자.

 

def outsideair():
    while stack:
        temp = stack.pop()
        x = temp[0]
        y = temp[1]
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if 0 <= nx < N and 0 <= ny < M:
                if cheeze[nx][ny] == 0:
                    cheeze[nx][ny] = -1
                    stack.append([nx,ny])
                elif cheeze[nx][ny] > 0:
                    cheeze[nx][ny] += 1
                    
outsideair()
melting = deque()

def melt(hour):
    while True:
        cnt = 0
        for n in range(N):
            for m in range(M):
                if cheeze[n][m] > 2:
                    melting.append([n,m])
        
        for i in range(len(melting)):
            temp = melting.pop()
            n = temp[0]
            m = temp[1]
            cnt += 1
            cheeze[n][m] = -1

            # 녹이고
            for d in range(4):
                nx = n + dx[d]
                ny = m + dy[d]
                
                if 0 <= nx < N and 0 <= ny < M and cheeze[nx][ny] > 0:
                    cheeze[nx][ny] += 1
                elif 0 <= nx < N and 0 <= ny < M and cheeze[nx][ny] == 0:
                    cheeze[nx][ny] = -1
                    stack.append([nx,ny])
        if stack:
            outsideair()
        if cnt == 0:
            print(hour)
            exit()

        hour += 1
melt(0)

 

녹인 치즈 자리에 사방탐색을 해서 치즈가 있다면 ( 주위 좌표의 값이 0보다 크다면 ) +1을 해준다. 

만약 내부 공기가 있다면 (값이 0이라면) stack에 추가해준다.

 

stack은 맨 처음에 무조건 0이였던 네 귀퉁이 ([0,0], [N-1,0], [0,M-1], [N-1,M-1]) 를 담고있던 스택이다.

그러면 stack에 담긴 좌표부터 사방탐색을 하여 주위 값에 내부공기(0) 이 있다면, 외부 공기(-1)로 바꿔주는 작업(outside)을 할 것이다.

 

 

 

그렇다면 이제 로직은 이렇다.

 

초기단계 :  네 귀퉁이(0) 에서 시작해 주변을 탐색해 외부공기(0)가 있다면 -1로 바꿔준다. 만약 치즈( > 0 )가 있다면 +1 을 해준다. (method : outside)

 

while문 1단계 : 이중 for문으로 맵 전체를 탐색하면서 외부 공기 2칸 이상 접촉한 (좌표의 값이 3이상) 친구는 deque(melting)에 저장한다.

 

while문 2단계 : deque(melting) 에 있는 좌표의 값을 -1 (치즈를 녹인다) 로 바꿔준다. 그리고 그 좌표에서 사방탐색을 하여 치즈가 있다면 ( > 0 ) +1해주고, 내부공기가 있다면 그 좌표를 stack에 담는다.

 

while문 3단계 : stack에 좌표가 담겨있다면 (2단계에서 외부공기와 내부공기가 접촉했다면) method : outside를 실행해서, 내부공기를 전부 -1로 바꾸고, 내부공기와 접촉한 치즈를 +1 한다.

 

4단계 : Profit!!!

 

 

결과는 대 성공이었다. 

그럼 안녕~~~~~~~~

 

 

 

 

 

... 하고 싶지만... 

 

하나 의문점이 드는 것이 굳이 while이 돌 때마다 이중 for문을 돌려야되냐는 것이다?

그냥 녹이는 치즈를 deque나 리스트에 저장해서 그 값에 대해서만 실행하면 되지 않을까

 

 

내가 생각했지만 생각해보니 그렇네

 

한번 구현해보자.

 

import sys
from collections import deque 

N, M = map(int,sys.stdin.readline().split())
cheeze = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
stack = [[0,0], [N-1,0], [0,M-1], [N-1,M-1]]
dx = [0,-1,0,1]
dy = [-1,0,1,0]
hour = 0

visited = [[0 for col in range(M)] for row in range(N)]
waiting = deque()


def outsideair():
    while stack:
        temp = stack.pop()
        x = temp[0]
        y = temp[1]
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if 0 <= nx < N and 0 <= ny < M:
                if cheeze[nx][ny] == 0:
                    cheeze[nx][ny] = -1
                    stack.append([nx,ny])
                elif cheeze[nx][ny] > 0:
                    cheeze[nx][ny] += 1
                    if cheeze[nx][ny] > 2 and visited[nx][ny] == 0:
                        waiting.appendleft([nx,ny])
                        visited[nx][ny] = 1


outsideair()


def melt(hour):
    while True:
        cnt = 0
        
        for i in range(len(waiting)):
            temp = waiting.pop()
            n = temp[0]
            m = temp[1]
            cnt += 1
            cheeze[n][m] = -1

            for d in range(4):
                nx = n + dx[d]
                ny = m + dy[d]
                
                if 0 <= nx < N and 0 <= ny < M and cheeze[nx][ny] > 0:
                    cheeze[nx][ny] += 1
                    if cheeze[nx][ny] > 2 and visited[nx][ny] == 0:
                        waiting.appendleft([nx,ny])
                        visited[nx][ny] = 1


                elif 0 <= nx < N and 0 <= ny < M and cheeze[nx][ny] == 0:
                    cheeze[nx][ny] = -1
                    stack.append([nx,ny])
        if stack:
            outsideair()
            
        if cnt == 0:
            print(hour)
            exit()

        hour += 1
melt(0)

 

결과는 대대성공이었다.

아래가 바꾸기 전, 위가 바꾼 후이다.

60ms나 줄은 것을 알 수 있다.

 

현재 백준 기준으로 파이썬 3위, 파이파이 1위인데 어제 시간초과되서 새벽까지 붙잡고있었던 것을 생각하면 뭔가 뿌듯하다.

 

 

그럼 여러분들도 맛있는 치즈를 드시기 바라면서 

안뇽~~~~~~~

 

 

댓글