[백준] 2636 치즈 python 풀이

문제

• 난이도: 골드4
• 알고리즘 분류: 구현, 그래프, 시뮬레이션, 너비 우선 탐색
• 요약: 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수 출력하기

 

풀이

공기와 접촉된 칸에 대한 처리

queue에 공기의 좌표를 담고 하나씩 값을 꺼내 공기와 접촉된 칸에 대해 녹이는 작업을 진행한다.
이때, 판의 가장자리에는 치즈가 놓여있지 않다는 전제에 따라 (0, 0)부터 탐색한다.
(0, 0)을 시작으로하면 치즈의 구멍에 대한 접근이 불가능한 것을 처리할 수 있다.

 

해당 좌표 값에 방문하지 않았을 경우에 대하여

• 공기일 경우: queue에 추가
• 치즈일 경우: 공기와 접촉되어 있으므로 해당 칸을 공기로 바꾸고 녹인 개수를 업데이트한다.
  (board[ny][nx] = 1 공기로 바꿔도 이미 해당 칸에 대한 방문을 처리했기 때문에 해당 칸에 대한 탐색을 중복으로 처리할 수 없다.)

 

 

코드

from collections import deque
import sys

input = sys.stdin.readline

r, c = map(int, input().split())

board = []
for _ in range(r):
	board.append(list(map(int, input().split())))

#     상  하  좌  우
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def bfs():
	queue = deque() # 공기
	queue.append([0, 0])
	visited[0][0] = True

	melt_count = 0 # 녹아야 될 부분

	while queue:
		y, x = queue.popleft()

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

			if 0 <= ny < r and 0 <= nx < c and visited[ny][nx] == False:
				visited[ny][nx] = True

				if board[ny][nx] == 0:
					queue.append([ny, nx])
				elif board[ny][nx] == 1:
					board[ny][nx] = 0
					melt_count += 1
	
	return melt_count

# 초기 치즈 개수 계산
cheese_count = 0
for y in range(r):
	for x in range(c):
		if board[y][x] == 1:
			cheese_count += 1

time = 0
while True:
	visited = [[False] * c for _ in range(r)]

	melt_count = bfs()
	time += 1
	cheese_count -= melt_count
	if cheese_count == 0: # cheese_count == melt_count
		break

print(time)
print(melt_count)