[Python 파이썬] 백준 2638번 - 치즈

2024년 6월 9일

문제 링크 : 백준 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은 하나의 공백으로 분리되어 있다.

출력

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

 

알고리즘 분류

• 구현
• 그래프 이론
• 그래프 탐색
• 시뮬레이션
• 너비 우선 탐색
• 깊이 우선 탐색

---

문제 접근

 

모눈종이의 특정 칸에 치즈가 놓여져 있고, 해당 치즈는 외부 공기와 닿는 면이 2개 이상인 경우 1시간 뒤에 녹는다.

 

여기서 주의해야 할 점은, 치즈로 둘러싸여져 있는 공기는 외부 공기가 아니라는 점이다. 어떤 치즈가 2개의 공기 블럭과 인접해 있어도, 하나가 치즈로 둘러싸여져 있는 내부 공기라면 해당 치즈는 녹지 않는 것이다. 이 점을 고려하여 문제에 접근해야 한다.

 

결국 매 time마다 외부공기가 어떤 블럭에 존재하는지 정확하게 알아야 녹을 치즈를 분별할 수 있기에, 매 사이클마다 bfs를 진행해 현재 시점의 보드에 존재하는 외부 공기 상태를 갱신시켜 주어야 한다.

 

그렇다면 매 보드의 bfs 시작점은 어디로 해야 하는가? 어느 케이스가 들어와도 무조건 외부공기일 수 밖에 없는 곳을 시작점으로 두어야 예외 사항이 없을 것이다. 이는 문제에서 힌트를 주었다.

 

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다.

 

구현 및 시뮬레이션 유형은 문제를 꼼꼼하게 읽어야 하는 이유이다.

 

bfs로 접근은 하고 싶은데, 시작점을 어디로 두어야 하지? 라고 고민한 점에 대한 해답은 저 한 문장에서 찾을 수 있었다.

 

모눈종이의 가장자리 어느 점을 시작점으로 두어도 상관이 없으니, 나는 매번 [0, 0]을 시작점으로 두고 bfs를 진행해 외부 공기 상태를 갱신시켜 주기로 하였다.

 

해당 점을 기준으로 bfs를 진행하면 1로 둘러 싸여있는 내부 공기는 탐색을 못하니 외부 공기와 내부 공기를 분간하는 결정적인 요인이 된다.

 

매 사이클마다 외부 공기 상태를 기준으로 각 치즈의 상/하/좌/우 2개 이상의 면이 외부 공기에 밀접해있다면 해당 치즈를 녹이고 사이클이 종료되면 time을 1씩 증가시켜 최종적으로 치즈가 0개가 됐을 때 time을 출력하면 된다.

---

순서도

 

1. 행과 열의 크기 N, M을 입력 받는다.

2. 모눈종이와 치즈의 상태를 담을 board를 선언한다.
2-1. 2차원 형태로 N줄에 걸쳐 board의 상태를 세팅하며, 각 행을 추가할 때마다 치즈의 개수 cnt를 함께 증가시킨다.

3. 메인 로직을 담당하는 solution 함수를 동작시킨다. 흐른 시간을 의미하는 time을 선언하며 초기값은 0이다.

4. 모눈종이에 남은 치즈의 수가 0이 될 때까지 반복문을 수행시킨다.
4-1. 매 순간마다 전체 모눈종이에서 외부공기가 어디있는지 정보를 담아낼 opened를 bfs 로직을 통해 알아낸다.
4-2. opened 배열을 기반으로, 각 모눈종이 칸의 치즈가 2개 이상의 외부공기에 노출되어 있는지 확인 후, 곧 녹을 치즈라면 will_melt에 append한다.
4-3. will_melt의 요소를 하나씩 pop() 해주며, 해당 치즈는 녹았다는 의미로 board의 해당 치즈 위치의 값을 1에서 0으로 치환시킨다. cnt 또한 1 감소시킨다.
4-4. 4-1 ~ 4-3의 과정을 모두 수행하면 time을 1 증가시킨다.

5. 반복문이 종료되면 time을 return 한다.

 

 

---

입력 예제

 

8 9
0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0
0 0 0 1 1 0 1 1 0
0 0 1 1 1 1 1 1 0
0 0 1 1 1 1 1 0 0
0 0 1 1 0 1 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

 

 

 

출력 예제

 

4

 

---

전체 코드

 

# 2638

import sys
from collections import deque

input = sys.stdin.readline

# 해당 칸이 외부공기인지 확인하는 메소드
def isValid(row, col, visited):
    if 0 <= row < N and 0 <= col < M:
        if not visited[row][col] and board[row][col] == 0:
            return True
    
    return False

def bfs(row, col, visited):
    # 동, 남, 서, 북
    d_row = [0, 1, 0, -1]
    d_col = [1, 0, -1, 0]

    queue = deque()
    queue.append([row, col])
    visited[row][col] = True

    while queue:
        now_v = queue.popleft()
        now_row = now_v[0]
        now_col = now_v[1]

        for i in range(4):
            next_row = now_row + d_row[i]
            next_col = now_col + d_col[i]
            if isValid(next_row, next_col, visited):
                queue.append([next_row, next_col])
                visited[next_row][next_col] = True
    
    return visited

def solution():
    global cnt
    time = 0

    # 동, 남, 서, 북
    d_row = [0, 1, 0, -1]
    d_col = [1, 0, -1, 0]

    while cnt > 0:
        # 매 사이클마다 bfs 수행, 노출되어있는 공간을 담을 opened 선언 및 세팅
        opened = bfs(0, 0, [[False for _ in range(M)] for _ in range(N)])
        
        will_melt = []

        for row in range(N):
            for col in range(M):
                if board[row][col] == 1:
                    # 노출된 면 개수
                    open_cnt = 0
                    for i in range(4):
                        if opened[row + d_row[i]][col + d_col[i]]:
                            open_cnt += 1
                    if open_cnt >= 2:
                        will_melt.append([row, col])
        
        while will_melt:
            melt = will_melt.pop()
            board[melt[0]][melt[1]] = 0
            cnt -= 1
        
        time += 1

    return time

if __name__ == "__main__":
    N, M = map(int, input().split())

    board = []
    
    cnt = 0

    for _ in range(N):
        row = list(map(int, input().split()))
        for x in row:
            if x == 1:
                cnt += 1
        board.append(row)
    
    print(solution())

 

 

---

풀이 후기

 

암시적 그래프 탐색법을 활용한 구현 및 시뮬레이션 문제였다.

처음 문제를 보았을 때, 어떻게 접근하는게 좋을지 적당히 고민한 이후, 외부/내부 공기 구분에 초점을 맞춰 bfs를 사용하는데 까지 도달할 수 있었다.