백준 2276 물 채우기

작성일 | In |

문제 링크

알고리즘

  • 자료구조
  • 다익스트라
  • 우선순위 큐
  • 그래프

비슷한 문제

풀이

물통(막대) 상태가 주어졌을 때, 물을 부어서 얼마만큼의 물이 고이는지 계산하는 문제다.

물이 고이려면 고이는 부분의 물통 높이가 주위 물통 높이보다 낮아야 한다.

  • 각 칸의 높이가 주어지면, 테두리 부분을 우선순위 큐에 집어넣는다.

  • 우선순위 큐 요소를 하나씩 확인할텐데, 만약에 테두리 안쪽 물통이 테두리 물통보다 높이가 더 높다면 안쪽 물통이 테두리 역할을 대신한다. 즉, 우선순위 큐에 새로 집어넣는다.

높이가 낮은 것부터 확인하기 위해서 우선순위 큐를 쓰는 것.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import heapq
import sys
input = sys.stdin.readline

m, n = map(int, input().split())

visited = [[0] * m for _ in range(n)]
heap = []

pot = []
for i in range(n):
    a = list(map(int, input().split()))
    for j in range(m):
        if i == 0 or i == n-1 or j == 0 or j == m-1:
            heapq.heappush(heap, (a[j], i, j))
            visited[i][j] = 1
            
    pot.append(a)
    
    
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def sol():
    answer = 0
    global visited
    
    while heap:
        height, x, y = heapq.heappop(heap)
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
        
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            
            if visited[nx][ny] == 0:
                visited[nx][ny] = 1
            
                if pot[nx][ny] > height:
                    heapq.heappush(heap, (pot[nx][ny], nx, ny))
                else:
                    answer += height - pot[nx][ny]
                    heapq.heappush(heap, (height, nx, ny))
                
    return answer


print(sol())