[Python] 백준 2636 - 치즈 문제 풀이

Overview

BOJ 2636번 치즈 Python 문제 풀이
분류: Graph Traversal (그래프 탐색), bfs

---

문제 페이지

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

---

풀이 코드 1 - BFS

from sys import stdin
from collections import deque
from typing import List


def bfs(row: int, col: int, board: List[List[int]]) -> int:
    dy = [1, -1, 0, 0]
    dx = [0, 0, 1, -1]
    visit = list([False] * col for _ in range(row))
    dq = deque([(0, 0)])
    visit[0][0] = True
    cnt = 0

    while dq:
        cy, cx = dq.popleft()
        for i in range(4):
            ny, nx = cy + dy[i], cx + dx[i]

            if 0 <= ny < row and 0 <= nx < col and not visit[ny][nx]:
                if board[ny][nx] == 0:
                    dq.append((ny, nx))
                elif board[ny][nx] == 1:
                    board[ny][nx] = 0
                    cnt += 1
                visit[ny][nx] = True

    return cnt


def main():
    def input():
        return stdin.readline().rstrip()

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

    time, cnts = 0, {}
    while True:
        cnts[time] = bfs(row, col, board)
        if cnts[time] == 0:
            break
        time += 1

    print(time)
    print(cnts[time - 1])


if __name__ == "__main__":
    main()

매 시간마다 좌표 (0, 0)에서부터 BFS 탐색을 통해 바깥 공기과 녹는 치즈를 확인한다. 탐색 과정에서 바깥 공기를 만나면 deque dq에 저장하고, 치즈를 만나면, 값을 0으로 바꾸고 cnt 변수에 1을 더한다. 그리고 탐색한 자리는 visit 값을 True로 변경하여, 중복되지 않게 한다. 이 과정을 치즈가 다 녹을 때까지 반복하여 답을 구한다.

---

풀이 코드 2 - 녹은 위치 저장

from sys import stdin
from collections import deque
from typing import List


board = []
row, col = 0, 0
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]


def bfs(y: int, x: int, visit: List[List[bool]]) -> deque[(int, int)]:
    if visit[y][x]:
        return deque()

    dq = deque([(y, x)])
    board[y][x] = -1
    visit[y][x] = True
    melted = deque()

    while dq:
        cy, cx = dq.popleft()
        for i in range(4):
            ny, nx = cy + dy[i], cx + dx[i]

            if 0 <= ny < row and 0 <= nx < col and not visit[ny][nx]:
                if board[ny][nx] == 0:
                    board[ny][nx] = -1
                    dq.append((ny, nx))
                elif board[ny][nx] == 1:
                    board[ny][nx] = 0
                    melted.append((ny, nx))
                visit[ny][nx] = True

    return melted


def main():
    def input():
        return stdin.readline().rstrip()
    global board, row, col

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

    time, cnts = -1, {}
    air = deque([(0, 0)])
    while True:
        visit = list([False] * col for _ in range(row))
        cnt = len(air)
        if cnt == 0:
            break

        cnts[time] = cnt
        for _ in range(cnt):
            y, x = air.popleft()
            air += bfs(y, x, visit)
        time += 1

    print(time)
    print(cnts[time - 1])


if __name__ == "__main__":
    main()

이전 풀이에서는 매번 좌표 (0, 0) 위치에서부터 bfs 탐색을 하기 때문에 이전에 이미 공기가 된 위치도 반복해서 탐색한다. 따라서 이번 풀이에서는 치즈가 녹아 새롭게 공기가 된 위치를 deque air 에 저장하여, 해당 위치에서부터 bfs 탐색을 진행한다.

채점 결과 수행 시간이 줄긴 했지만, 이전과 많이 차이나지는 않는다.