[python] 백준 - 2573 (빙산)
골드4 문제이며, 제한 시간은 1초이다.
문제
해결 과정
BFS를 이용해서 빙산을 녹이고, 빙산의 개수까지 세준다. 처음에는 빙산을 녹일 때 즉시 녹이는 방법으로 했었다. 하지만 이 방식은 0으로 바뀐 빙산이 바로 영향을 줄 수 있기에 얼만큼 녹아야하는지 따로 저장해두고, 한 번에 녹이는 것이 중요하다. 이 아이디어만 있다면 그리 어렵지 않은 문제이다.
풀이
from collections import deque
def bfs(x, y):
queue = deque()
queue.append((x, y))
visited[x][y] = True
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 and not visited[nx][ny]:
if graph[nx][ny] == 0:
melt[x][y] += 1
else:
visited[nx][ny] = True
queue.append((nx, ny))
n, m = map(int, input().split())
graph = []
for _ in range(n):
graph.append(list(map(int, input().split())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
time = 0
while True:
melt = [[0 for _ in range(m)] for _ in range(n)]
visited = [[False for _ in range(m)] for _ in range(n)]
cnt = 0
#빙산 개수와 녹일 정보 얻기
for i in range(n):
for j in range(m):
if graph[i][j] > 0 and not visited[i][j]:
bfs(i, j)
cnt += 1
#빙산 녹이기
for i in range(n):
for j in range(m):
if melt[i][j] > 0:
graph[i][j] = max(graph[i][j] - melt[i][j], 0)
if cnt == 0:
print(0)
break
elif cnt > 1:
print(time)
break
time += 1
댓글
0아직 댓글이 없습니다.