[BOJ 2638 파이썬] 치즈 BFS

2638번: 치즈

 

난이도: 골드 3✅

풀이

---

골드 3이긴 하나 전형적인 BFS문제여서 크게 어렵진 않았다.

 

모눈종이의 크기와 같은 visited배열을 만들어서,

 

만약 치즈가 있는 칸이 아닌 곳이라면 visited[y][x] + 1 해주고,

치즈가 있는 칸을 만났다면,visited[y][x] + 2 해준다.

 

이렇게 해주는 이유는 다음번 방문 때 visited가 1이라면 그냥 넘어가 주어야 하고,

visited가 2라면 치즈에 이미 한번 방문했다는 것이므로, 두면이 공기에 접촉하고 있다고 볼 수 있다.

이때, 지워지는 치즈의 좌표들을 리스트에 저장해 전부 탐색한 이후 해당 리스트를 반환해준다.

 

이 작업을 반목문으로 그냥 0,0 좌표부터 BFS를 돌리면서 반환받은 치즈 배열의 좌표를 통해 모눈종이 배열을 업데이트 하고 치즈배열의 길이가 0이라면 치즈가 다 녹은 것이므로, 답을 반환한다. 

 

답

---

from collections import deque
import sys

N, M = map(int,sys.stdin.readline().rstrip().split())

board = []

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

dx = [1,0,-1,0]
dy = [0,-1,0,1]

def BFS():
    q = deque()
    q.append((0,0))
    visited = [[0 for _ in range(M)]for __ in range(N)]
    visited[0][0] = 1
    cheese = []
    while q:
        y,x = q.popleft()

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if 0 <= ny < N and 0 <= nx < M:
                if visited[ny][nx] == 0:
                    if board[ny][nx] == 1:
                        visited[ny][nx] += 2
                    else:
                        visited[ny][nx] += 1
                        q.append((ny,nx))
                elif visited[ny][nx] == 1:
                    pass
                elif visited[ny][nx] == 2:
                    #두번째 접촉
                    cheese.append((ny,nx))
    return cheese

answer = 0

while True:
    answer += 1
    cheese = BFS()
    for y,x in cheese:
        board[y][x] = 0
    if len(cheese) == 0:
        print(answer-1)
        exit()

 

골드3이지만 BFS를 많이 풀어보았다면 쉬웠던 문제이다.✌