[백준] 29761 : 물 뿌리기

https://www.acmicpc.net/problem/29761

문제 분석

 해당 문제를 단순히 접근하면 이미 방문한 노드를 다시 방문해야 되는 문제가  생긴다. 예를 들어 아래와 같은 경우를 생각해 보자 높이가 5인 노드를 나중에 방문하면 우상단의 노드가 4의 값을 가지고 나중에 5인 노드를 거쳐서 우상단의 노드롤 재방문해야될 필요가 생긴다. 노드의 재방문을 허락하게 되면 못 풀 거야 없지만 문제를 굉장히 어렵게 풀도록 된다. 그래서 우리는 노드를 한 번만 방문해도 되도록 몇 가지 규칙을 세우고 노드를 방문하도록 하겠다.

재방문이 강제된다.

 노드를 한번만 방문하기 위해서는 해당 노드를 방문하기 전 인접 노드 중 가장 큰 확산값을 줄 수 있는 노드를 먼저 방문해야 된다.그럼 가장 큰 확산 값을 주는 인접노드는 어떤 노드인가? 먼저 해당 노드보다 높이가 높은 노드의 경우 물의 양을 X로 만들어주므로 가장 우선순위가 높다. 그 다음 우선순위는 같은 높이의 노드중 그나마 물의 양이 가장 큰 노드이다. 같은 높이의 경우 물의 양을 1씩 깎아서 확산되므로  물의 양이 클수록 유리하다.

노드 방문 우선 순위
1. 높이가 높은 노드를 먼저 방문한다.
2. 높이가 동일한 경우  물의 양이 더 큰 노드를 방문한다.

따라서 (높이, 물의 양)을 key로 해서 우선순위 큐를 구성하면 된다. 이러한 방식이면 한 번의 방문만으로도 최대 물의 양을 보장 가능하다.

문제 해결 전략

 이제는 단순한 우선순위 큐 문제이다. 위의 키를 바탕으로 구현만 하면 된다. 다만, 1보다 큰 물의 양에서만 확산된다라는 사실을 주의하자 그러니깐 물의 양이 1인 곳에서 다른 곳으로 높이가 더 낮은 지점으로라도 확산은 일어나지 않는다. 아마 저조한 정답률은 이 조건을 놓쳐서이기 때문인 것 같다.    

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

//문제분석
//문제를 그냥 단순히 접근하면 왔던곳을 다시 방문해야 되는 문제가 생긴다.
//이런 경우에는 방문한 곳을 다시 방문하지 않도록 하는 방법이 필요하다. 
//재방문을 하지 않기 위해서는 특정 지점 방문시 그 지점의 물의 양이 최대 이미 수렴함을 보장해야 한다.  
//해당 지점의 물의 양이 최대 수렴함을 보장하기 위해서는 2가지 조건을 만족해야한다.
//1. 인접 지점 중 해당 지점 보다 높은 곳을 먼저 방문한다.
//2. 인접 지점 중 해당 지점과 높이가 같은 곳 중 물의 양이 많은 곳을 먼저 방문한다.
//전형적인 우선 순위 큐문제이다.
//그래프 탐색이 되 높이가 높은 지점을 먼저(1번 조건), 높이가 같을 경우 BFS를 따라 방문(2번 조건)
//물은 기본적으로 높이가 같거나 낮은 곳으로만 확산한다.
//
//N\in[1,2000], X\in[1,2N], x,y\in[1,N]
//=====================================================================
//해결전략
//1.
//=====================================================================
//필요자료형
//변수
//
//함수
//
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int main()
{
    int N,X,x,y;
    cin >> N >> X >> x >> y;
    vector<vector<int>> heights(N, vector<int>(N,0));
    vector<vector<int>> waters(N, vector<int>(N,0));
    vector<vector<bool>> visited(N, vector<bool>(N,false));
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            cin >> heights[i][j];

    priority_queue<pair<pair<int,int>,pair<int,int>>> q;
    q.push(make_pair(make_pair(heights[x-1][y-1],X),make_pair(x-1,y-1)));
    waters[x-1][y-1] = X;
    visited[x-1][y-1]=true;

    while(!q.empty()){
        int i = q.top().second.first;
        int j = q.top().second.second;
        q.pop();

        if(waters[i][j] <= 1) continue;

        for(int k=0; k<4; k++){
            int ni = i + dx[k];
            int nj = j + dy[k];

            if(ni < 0 || ni >= N || nj < 0 || nj >= N) continue;
            if(visited[ni][nj]) continue;

            if(heights[i][j] == heights[ni][nj]){
                waters[ni][nj] = waters[i][j]-1;
                visited[ni][nj]=true;
                q.push(make_pair(make_pair(heights[ni][nj],waters[ni][nj]),make_pair(ni,nj)));
            }
            else if(heights[i][j] > heights[ni][nj]){
                waters[ni][nj] = X;
                visited[ni][nj]=true;
                q.push(make_pair(make_pair(heights[ni][nj],waters[ni][nj]),make_pair(ni,nj)));
            }
        }
    }

    int result(0);
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            if (waters[i][j] > 0) result++;

    cout << result << endl;
}