[Baekjoon] 2638_치즈

Gold IV

문제(출처: https://www.acmicpc.net/problem/2638)

---

<치즈>

문제 

 

N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4 변 중에서 적어도 2 변 이상이 실내온도의 공기와 접촉한 것은 정확히 한 시간 만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

<그림 1>

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부 공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

<그림 2>

<그림 3>

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

 

 

입력

 

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

 

 

출력 

 

출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

 

 

문제 풀이

   - my solution (Python)

import sys
from collections import deque

def cheese(arr,queue,visited,cheese_temp):
    cheese_cnt = [[0] * m for i in range(n)] # 공기와 접촉한 변 개수
    dx=[-1,1,0,0] # 상하좌우
    dy=[0,0,-1,1]

    while queue:
        temp=queue.popleft()
        for i in range(4):
            x=temp[0]+dx[i]
            y=temp[1]+dy[i]
            if 0<=x<len(arr) and 0<=y<len(arr[0]): # 범위 안
                if arr[x][y]==0 and visited[x][y]==0: # 공기 - 방문 x
                    visited[x][y]=1
                    queue.append([x,y])
                elif arr[x][y]==1: # 치즈
                    if visited[x][y]==0: # 방문 x
                        cheese_cnt[x][y]+=1
                        visited[x][y] = 1
                    else: # 치즈 - 공기 2변 이상
                        cheese_temp.append([x,y])
    return cheese_temp

if __name__=='__main__':
    n,m=map(int,sys.stdin.readline().split())

    arr=[]
    for i in range(n):
        arr.append(list(map(int,sys.stdin.readline().split())))

    visited=[[0]*m for i in range(n)] # 방문 여부

    queue=deque([[0,0]])
    cheese_temp=deque([])
    visited[0][0] = 1

    day=0
    cheese_temp=cheese(arr,queue,visited,cheese_temp)
    for i in cheese_temp: # 치즈 -> 공기
        arr[i[0]][i[1]]=0

    while cheese_temp:
        day+=1
        cheese_temp = cheese(arr, cheese_temp, visited, deque([]))
        for i in cheese_temp:
            arr[i[0]][i[1]] = 0

    print(day)

 

상하좌우를 확인하여 공기이며 아직 방문하지 않았으면 방문 표시를 하며 계속해서 탐색해줍니다.

만약 치즈이며 아직 방문하지 않았으면 공기와 접촉한 변 +1을 해줍니다. 치즈인데 방문했었다면 공기와 접촉한 변이 2 변 이상이라는 뜻이므로 녹을 치즈 목록에 추가해줍니다.

 

 

• cheese( 입력 정보, queue, 방문 여부, 녹을 치즈 저장 )
  : cheese_cnt = 공기와 접촉한 변 개수 저장
  : 상하좌우를 탐색하여 그 값이 공기이며 아직 방문하지 않은 곳이라면 방문 표시 및 계속해서 탐색. 그 값이 치즈이며 아직 방문하지 않았다면 방문 표시 및 공기와 접촉한 변을 +1로 저장. 방문했던 곳이라면 공기와 접촉한 변이 2 변 이상이라는 뜻이므로 녹을 치즈 목록에 저장
  : cheese_temp = 녹을 치즈 목록 반환
• Main
  : 가로, 세로 크기 입력
  : arr 정보 입력
  : visited = 방문 여부
  : cheese_temp = 녹을 치즈 저장 ( 한 번에 녹아야 하므로 따로 저장해뒀다가 치즈 -> 공기로 바꿔줌 )
  : 녹을 치즈가 더 이상 없을 때까지 반복 -> 시간 +1 , 함수 호출 및 ( 치즈 -> 공기 ) 변환
  : 모두 녹아 없어지는데 걸리는 정확한 시간 출력

 

---

생각🤔

 

이 문제와 비슷한 문제를 해결해봐서 그런지 쉽게 해결할 수 있었다.

 

---