https://www.acmicpc.net/problem/15730
| 시간 제한 | 메모리 제한 |
| 2초 | 128 MB |
문제
수영장 사업을 시작하려는 수형이는 산의 자연을 훼손하지 않고 지형을 그대로 이용한 수영장을 만들기로 한다. 그래서 물이 고일 수 있는 부분에만 물을 채워넣는 방법을 사용하기로 한다. 이때 수형이는 여기서 얼마만큼의 물을 채울 수 있는지 궁금해 하는데, 땅의 정보가 주어졌을 때 얼마만큼의 물을 채울 수 있는지 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 N, M(1 ≤ N, M ≤ 100)가 주어진다. 다음 N 줄동안 매 줄마다 M개의 H(0 ≤ H ≤ 10,000)가 주어진다. 여기서 i 번째 줄의 j 번째 정수를 H[i][j] 라고 할 때, H[i][j]는 해당하는 땅의 높이이다.
출력
최대한 물을 채웠을 때 얼마만큼의 물을 채울 수 있는지를 출력한다.
풀이
이 문제는 풀이가 두 가지입니다. 먼저 시간을 많이 잡아먹지만 직관적인 BFS 풀이가 있고, 빠르지만 엥? 싶은 다익스트라 풀이가 있습니다. 직관적인 것부터 봅시다.
1. BFS로 풀기
높은 지점부터 인접한 칸으로 탐색을 시도합니다. 탐색이 시작된 곳의 높이를 h라고 했을 때 h보다 낮거나 같은 칸들을 같은 영역으로 묶습니다. 탐색을 진행하면서 만나는 h보다 높은 칸들은 영역을 둘러싼 벽이 됩니다. 만약 탐색 도중에 영역이 주어진 그리드의 테두리 부분과 닿아버렸다면 해당 영역은 물이 채워질 수 없습니다. 이 경우는 다음 높이를 탐색합니다. 탐색이 모두 끝났다면 만난 벽들 중 높이가 가장 낮았던 곳으로 탐색한 모든 영역의 칸에 물을 채울 수 있습니다.
초록색 위치에서 탐색을 시작하면 노란색 영역이 주황색으로 둘러싸이게 됩니다. 주황색 중 가장 높이가 낮은 곳은 7입니다. 이번에 탐색한 영역은 최소한 높이 7까지 물을 채울 수 있습니다. 물 높이를 관리할 2차원 배열에 탐색 결과로 높일 수 있는 물 높이를 관리해줍니다.
이 방법을 그대로 적용했더니 시간초과가 발생했습니다. 높은 지점부터 탐색하기 때문에 높은 지점으로부터 한 영역이 발생한 경우, 그 영역 내의 모든 부분은 앞으로 탐색할 필요가 없게 됩니다. (더 낮은 곳에서 탐색을 시작하기 때문에 의미 없음) 따라서 이미 영역으로 처리가 되었던 칸은 다시 탐색하지 않도록 해야 합니다.
여기까지 하면 일단 시간 내에 문제가 해결 되기는 하지만 유니온 파인드를 이용해 더 최적화할 수 있다고 합니다.
2. 다익스트라(?)로 풀기
다익스트라 라고는 하는데 풀이 설명을 아무리 봐도 이게 왜 다익스트라인지 모르겠습니다. 일단 최소힙을 활용하기는 합니다.
수영장의 가장 바깥쪽 테두리만 최소힙에 추가합니다. 이 힙에 들어있는 모든 칸이 움직이는 벽이라고 생각하면 이해하기 편합니다. 이 힙에 대해 다음과 같은 과정을 반복합니다.
- 힙에서 데이터를 꺼낸다. 꺼낸 위치 (x, y)는 현재의 벽에서 가장 높이가 낮은 곳임이 보장된다. 즉, (x, y)로부터 벽 안쪽은 최소한 (x, y)만큼의 높이를 만들 수 있다.
- (x, y)로부터 인접한 칸을 탐색한다. 벽 바깥쪽은 이미 탐색을 했고, 벽 역시 이미 탐색이 되었기 때문에 벽 안 쪽만 탐색하게 된다. 여기서 두 가지 경우로 나뉜다.
- 현재 위치 (x, y)보다 벽 안 쪽 (x', y')의 높이가 더 낮은 경우
→ 벽 안 쪽 (x', y')의 높이를 (x, y)의 높이 만큼 높여줄 수 있다. 높이를 갱신시키고 (x', y')를 힙에 추가해 벽을 좁힌다. - 현재 위치 (x, y)보다 벽 안 쪽 (x', y')의 높이가 같거나 더 높은 경우
→ (x', y')를 힙에 추가해 벽을 좁힌다.
- 현재 위치 (x, y)보다 벽 안 쪽 (x', y')의 높이가 더 낮은 경우
- 벽이 모두 좁혀져 사라질 때까지(힙이 비워질 때까지) 1과 2를 반복한다.
굉장히 간단한 작업이지만 아이디어가 생각하기 어렵습니다.
문제의 예제 입력 1을 돌려보면 이런 식으로 됩니다. 2행 1열의 3이 2행 2열의 2보다 높습니다. 2행 2열의 값을 3으로 바꾸면서 새로운 벽으로 바꿔줍니다. 이 다음은 다시 2행 2열의 3이 3행 2열의 1을 3으로 높이게 됩니다.
정답 코드
# BFS 풀이
import sys
from heapq import heappush, heappop
from collections import deque
input = sys.stdin.readline
def solution():
n, m = map(int, input().split())
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
pool = [[0 for _ in range(m + 2)]] + [[0] + list(map(int, input().split())) + [0] for _ in range(n)] + [[0 for _ in range(m + 2)]]
fill = [[0] * (m + 2) for _ in range(n + 2)]
hq = []
res = 0
for i in range(1, n + 1):
for j in range(1, m + 1):
heappush(hq, (-pool[i][j], i, j))
while hq:
h, i, j = heappop(hq)
if fill[i][j] > 0: continue
border = 10001
bfs = deque([(i, j)])
area = set()
area.add((i, j))
while bfs:
x, y = bfs.popleft()
for dx, dy in d:
nx, ny = x + dx, y + dy
if 0 < nx <= n and 0 < ny <= m:
if pool[nx][ny] > pool[i][j]:
border = min(border, pool[nx][ny])
elif fill[nx][ny] == 0 and not((nx, ny) in area):
bfs.append((nx, ny))
area.add((nx, ny))
else:
bfs.clear()
area.clear()
break
if border < 10001:
for x, y in area:
fill[x][y] = border
res += max(fill[x][y] - pool[x][y], 0)
print(res)
solution()
# 다익스트라
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
n,m = map(int, input().split())
pool = [list(map(int, input().split())) for _ in range(n)]
check = [[0] * m for _ in range(n)]
wall = []
result = 0
for i in range(m):
heappush(wall, (pool[0][i], 0, i))
check[0][i] = 1
for i in range(1, n):
heappush(wall, (pool[i][0], i, 0))
check[i][0] = 1
if n > 1:
for i in range(1, m):
heappush(wall, (pool[-1][i], n - 1, i))
check[-1][i] = 1
if m > 1:
for i in range(1, n - 1):
heappush(wall, (pool[i][-1], i, m - 1))
check[i][-1] = 1
while wall:
h, x, y = heappop(wall)
for dx, dy in d:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < m and check[nx][ny] == 0:
check[nx][ny] = 1
if pool[nx][ny] < h:
result += h - pool[nx][ny]
pool[nx][ny] = h
heappush(wall, (pool[nx][ny], nx, ny))
print(result)
