BOJ - 치즈 2636번 (python)

❓ 문제 - 백준 치즈 2636번 - python 풀이법

출처 

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

2636번: 치즈

 

 

📝 문제해결법

1. 이 문제의 핵심은 그래프탐색(BFS)을 이용하여 푸는 것이다.

• 처음 모든 칸을 돌면서 치즈(1 값)이 존재하는지 탐색하고 치즈 값이 있다면 cheese 값을 카운트
• 만약 cheese 값이 존재하다면 BFS를 돌면서 0인 경우에서 네방향으로 탐색하여 만약 1값 (공기에 둘러싼 값)이 있다면 방문처리하고 녹게 처리(값을 0으로 변경)
• 네방향 탐색 시 방문하지 않은 0값이라면 q에 append

2. 메인 코드

• check()을 활용하여 모든 graph를 돌면서 치즈가 남아 있는지 확인하고, 몇 장의 치즈가 남았는지 return
• 만약 남은 치즈의 갯수가 0개 이상이라면 BFS를 돌려서 공기와 접촉된 칸의 치즈가 녹게 하고, time을 증가시키며 녹기 전에 치즈 값을 last_cheese 변수를 사용하여 저장
• 만약 남은 치즈의 갯수가 0개 (즉, 모두 녹거나 치즈가 존재하지 않음)라면 while 문을 빠져나가서 정답인 time과 last_cheese를 출력

 

 

💻 소스코드

# 치즈 - BOJ 2636
# BFS
import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(a, b):
    visited = [[False]*m for _ in range(n)]
    q = deque()
    q.append((a, b))
    visited[a][b] = True
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if visited[nx][ny] == False:
                    if graph[nx][ny] == 1:
                        graph[nx][ny] = 0
                        visited[nx][ny] = True
                        continue
                    if graph[nx][ny] == 0:
                        visited[nx][ny] = True
                        q.append((nx, ny))

def check():
    one_count = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                one_count += 1
    return one_count


time = 0
last_cheese = 0

while True:
    cheese = check()
    if cheese > 0:
        bfs(0, 0)
        time += 1
        last_cheese = cheese
    elif cheese == 0:
        break

print(time)
print(last_cheese)