[Python] 백준 2636번 문제, 치즈

<문제 링크>

 

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

2636번: 치즈

 

---

<풀이>

 

이 문제는 너비우선탐색을 이용한 시뮬레이션 문제이다.

보드판 위에 치즈가 있을 때, 치즈는 1개의 블록의 집합으로 이루어져있는데

1시간마다 치즈의 겉테두리이 녹는다.

즉, 치즈의 테두리가 1시간마다 사라진다는 것이다.

 

치즈 중간이 비어있어도 겉테두리와 연결되어 있지 않다면 녹지 않으며, 무조건 겉테두리만 1시간에 한 번씩 녹는다.

그래서 너비우선탐색으로 치즈의 겉테두리를 찾아낸 다음에 겉테두리 값을 1(치즈)에서  0(빈 블록)으로 변경시켜준다.

변경 시키는 방법은 BFS를 통해 겉테두리 좌표값을 next_que에 저장한 다음에 board에서 값을 변경해준다.

그리고 next_que는 겉테두리와 근접한 빈 블록이기 때문에 que=next_que로 선언해주면 처음부터(0, 0) 겉테두리를 찾을 필요가 없다.

 

마지막에 return에서 time-1를 해준 이유는, 맨 처음부터(0, 0) 겉테두리를 찾는 시간이 포함됐기 때문이다.

따라서 녹은게 걸린 시간만 필요하기 때문에 처음 겉테두리에 걸린 시간 1을 빼줘 return time-1이다.

 

---

<코드>

time: 치즈가 다 녹는데 걸리는 시간

count: 마지막에 녹을 치즈 갯수

que[]: 현재 포커싱 큐

next_que[]: 다음에 탐색할 큐

board[][]: (w, h)인 맵

visited[]: 방문 여부 리스트

move[]: 움직일 좌표를 튜플로 저장

---

import sys


def bfs():
    time = 0 # 소비 시간
    count = 0 # 마지막 치즈 갯수
    que = [(0, 0)] # 현재 포커싱 큐
    next_que = [] # 다음 포커싱 큐

    while que:
        time += 1 # 시간 증가
        count = len(que)

        # 녹일 치즈 좌표 구하기
        for i, j in que:
            if not visited[i][j] and board[i][j] == 0:
                visited[i][j] = True

                for di, dj in move:
                    dx = i + di
                    dy = j + dj

                    if 0 <= dx < w and 0 <= dy < h:
                        if board[dx][dy] == 0:
                            que.append((dx, dy))
                        else:
                            if not (dx, dy) in next_que:
                                next_que.append((dx, dy))
        # 치즈 녹이기
        for i, j in next_que:
            board[i][j] = 0

        # 녹은 치즈 좌표에서 너비 우선 탐색 수행하기
        que = next_que.copy()
        next_que = []
                        
    return time-1, count


if __name__ == '__main__':
    w, h = map(int, sys.stdin.readline().rstrip().split())
    board = []
    visited = [[False for _ in range(h)] for _ in range(w)] # 방문 여부
    move = [(0, -1), (1, 0), (0, 1), (-1, 0)] # 상우하좌

    for _ in range(w):
        board.append(list(map(int, sys.stdin.readline().rstrip().split())))

    time, count = bfs()

    print(time)
    print(count)