[Python] 백준2638 치즈

29 Jun 2023 in Study on Algorithm

백준2638 치즈 링크

문제

예제 입력

---

코드

import sys
from collections import deque
    
def outsideBFS():
    q = deque()
    q.append([0, 0])
    tmp[0][0] = -1

    while q:
        x, y = q.popleft()
        for dx, dy in [[-1, 0],[1, 0],[0, -1],[0, 1]]:
            newx = x + dx
            newy = y + dy

            if 0 <= newx < n and 0 <= newy < m:
                if tmp[newx][newy] == 0:
                    tmp[newx][newy] = -1
                    q.append([newx, newy])

n, m = map(int, input().split())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

ans = 0
while True:
    q = deque()
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 1:
                q.append([i, j])
    if len(q) == 0:
        break

    # 채워야함.copy()는 주소참조
    tmp = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            tmp[i][j] = arr[i][j]
    outsideBFS()
    
    while q:
        x, y = q.popleft()
        cnt = 0
        for dx, dy in [[-1, 0],[1, 0],[0, -1],[0, 1]]:
            newx = x + dx
            newy = y + dy

            if 0 <= newx < n and 0 <= newy < m:
                if tmp[newx][newy] == -1:
                    cnt += 1
        if cnt >= 2:
            arr[x][y] = 0
    ans += 1

print(ans)

설명

파이썬을 통해서 사용자로부터 입력받아 BFS 알고리즘을 사용하여 치즈를 구현했습니다.

---

결과