문제 설명
https://www.acmicpc.net/problem/2636
문제 풀이
처음에는 치즈의 구멍을 고려하지 않고 문제를 풀었더니 당연히 실패 ...
공기가 있는 부분을 탐색하는 BFS랑, 치즈 조각을 탐색하는 BFS로 두 개의 함수를 사용하였다.
치즈 조각을 탐색하면서 근처에 공기가 한 칸이라도 있으면, set에 넣은 후
치즈가 녹는 부분들을 공기로(0으로) 만들어주었다.
그 후 공기 탐색 BFS 때 음수로 처리해주었던 공기 칸들을 다시 0으로 만들어주었다.
from collections import deque
def air_bfs():
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if board[nx][ny] == 0:
queue.append((nx, ny))
board[nx][ny] = -1
def cheese_bfs():
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if board[nx][ny] == 1:
queue.append((nx, ny))
board[nx][ny] = board[x][y] + 1
if board[nx][ny] < 0:
melt.add((x, y))
n, m = list(map(int, input().split()))
board = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
melt = set()
queue = deque()
cnt = 0
while True:
queue.append((0, 0))
air_bfs() # 공기 BFS
positive = False
# 치즈가 남아있는지 검사
for i in range(n):
for j in range(m):
if board[i][j] > 0:
positive = True
break
if positive:
break
# 모두 녹았을 때
if not positive:
print(cnt)
print(len(melt))
break
# 치즈가 남아있을 때
else:
cnt += 1
rst = 0
melt.clear()
# 치즈 부분 BFS
for i in range(n):
for j in range(m):
if board[i][j] > 0:
queue.append((i, j))
cheese_bfs()
# 녹는 부분 공기로 만들기
for mt in melt:
x, y = mt
board[x][y] = 0
# 공기 부분 다시 0으로 만들기
for i in range(n):
for j in range(m):
if board[i][j] < 0:
board[i][j] = 0
'알고리즘 > 백준' 카테고리의 다른 글
[백준`G5] 2294 - 동전 2 (Python) (0) | 2024.03.22 |
---|---|
[백준`S1] 14888 - 연산자 끼워넣기 (Python) (2) | 2024.03.22 |
[백준`G5] 7569 - 토마토 (Python) (0) | 2024.03.14 |
[백준`G5] 13023 - ABCDE (Python) (1) | 2024.03.08 |
[백준`S1] 1932 - 정수 삼각형 (Python) (0) | 2024.03.06 |