백준 문제/BFS,DFS
[필수]백준: 치즈_2636
goldpig
2024. 2. 1. 14:21
728x90
https://www.acmicpc.net/problem/2636
2636번: 치즈
첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진
www.acmicpc.net
핵심 아이디어
- 외부 공기와 접촉한 치즈만을 녹이기 위해서는 값이 0인 부분만 BFS를 적용
- 초기 전체 치즈의 개수를 구해서 시간 마다 녹은 치즈의 개수를 뺀다.
- BFS 알고리즘 - 시간 마다 녹은 치즈의 개수를 반환, 그리고 치즈를 한번에 제거한다.
- 치즈가 다 녹으면 시간과 직전 치즈 개수 반환 그렇지 않으면 시간 +1
구현 코드
'''
외부 공기와 접촉한 치즈만을 녹이기 위해서는 값이 0인 부분에
대해서만 BFS 진행
치즈가 다 녹았는지 어떻게 알 수 있나? 판의 초기 상태에서 치즈의 개수를
먼저 카운트한다.
'''
import sys
input = sys.stdin.readline
from collections import deque
n,m = map(int, input().split())
graph = []
cnt = 0 # 전체 치즈의 개수를 카운트하기 위한 변수
for i in range(n):
graph.append(list(map(int, input().split())))
cnt += sum(graph[i])
# 이동을 위한 방향 정의
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def bfs():
# bfs의 시작지점은 가장 자리의 한 지점에서 가능
# 판의 가장자리에는 치즈가 놓여 있지 않다
q = deque([(0,0)])
melt = deque([]) # 녹은 치즈를 담기위한 deque
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) and not visited[nx][ny]:
visited[nx][ny] = 1 # 방문처리
if graph[nx][ny] == 0: # 공기면 계속 탐색히가 위해 큐에 넣음
q.append((nx,ny))
elif graph[nx][ny] == 1: # 치즈면 한번에 녹이기 위해 melt에 담아
melt.append((nx,ny))
# 한번에 치즈 녹이기
for x,y in melt:
graph[x][y] = 0 # 공기와 닿은 치즈를 한번에 녹임
return len(melt) # 녹은 치즈의 수 반환
time = 1
while True:
visited = [[0] * m for _ in range(n)]
meltCnt = bfs() # 녹은 치즈의 개수
cnt -= meltCnt
if cnt == 0: # 치즈가 다 녹으면
print(time, meltCnt, sep='\n')
break
else:
time += 1 # 다 녹지 않았으면 한 시간 추가
728x90