물 채우기
문제 해석
NxM크기의 물통에 물을 부었을 때, 담을 수 있는 물의 최대량을 계산하는 문제입니다.
물의 테두리도 높이가 다를 수 있고, 테두리가 물통의 안쪽보다 높이가 낮을 수도 있습니다.
설계(X)
문제의 접근법조차 쉽지 않았던 문제였습니다.
처음에 이분탐색 + dfs를 하면 되지 않을까 생각했지만 논리적으로 봤을 때 정해가 아니었습니다.
해당 블로그의 아이디어를 참조하였습니다.
이분의 풀이는 테두리부터 시작해서 낮은 수면부터 채워나가는 방식으로 되어있습니다.
낮은 수면부터 채워나가기 위해서 우선순위 큐를 사용합니다.
각 좌표에서 dfs탐색을 하면서 기준 수면보다 높은 좌표가 나오면 pq에 넣고, 그렇지 않으면 기준 수면까지 물을 채우는 방식으로 진행합니다.
구현(X)
코드
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
#define MAXN 300
int N,M;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
bool visited[MAXN][MAXN];
int arr[MAXN][MAXN];
int ans;
bool flag;
struct node{
int x,y,h;
bool operator <(const node& a)const{
return a.h < h;
}
};
priority_queue<node> pq;
void dfs(int x, int y, int height){
for (int i = 0 ; i< 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx>=N || ny>=M || visited[nx][ny]) continue;
visited[nx][ny] = true;
if (arr[nx][ny] > height) pq.push({nx,ny,arr[nx][ny]});
else{
ans += height - arr[nx][ny];
dfs(nx,ny,height);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> M >> N;
for (int i = 0 ; i < N; i++){
for (int j= 0;j<M;j++){
cin >> arr[i][j];
if (i == 0 || j == 0 || i == N-1 || j == M-1) {
pq.push({i,j,arr[i][j]});
visited[i][j] = true;
}
}
}
while (!pq.empty()){
int x = pq.top().x;
int y = pq.top().y;
pq.pop();
dfs(x,y,arr[x][y]);
}
cout << ans <<"\n";
return 0;
}
디버깅
제출결과
12 ms
마무리
우선순위큐를 활용한 dfs문제였습니다.
문제를 해결하기 위해서 발상의 전환이 필요한 문제인 것 같습니다.