[Algorithm]Baekjoon 2276번 : 물 채우기

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

2276번: 물 채우기

 
 
using namespace std;
 
 
struct Node
{
    int y;
    int x;
    int height;
};
 
struct cmp
{
    bool operator() (const Node& a, const Node& b)
    {
        return a.height > b.height;
    }
};
 
int col, row;
int arr[301][301] = { 0 };
bool visited[301][301] = { false };
int dirs[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
long long answer = 0;
priority_queue<Node, vector<Node>, cmp> pq;
 
bool isEdge(int y, int x)
{
    if (y >= 1 && y <= row - 2 && x >= 1 && x <= col - 2) return false;
    return true;
}
 
void solve()
{
    while (!pq.empty())
    {
        int curY = pq.top().y;
        int curX = pq.top().x;
        int curHeight = pq.top().height;
        pq.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dirs[i][0];
            int nextX = curX + dirs[i][1];
            
            if (nextY < 0 || nextY == row) continue;
            if (nextX < 0 || nextX == col) continue;
            if (visited[nextY][nextX]) continue;
 
            visited[nextY][nextX] = true;
 
            if (arr[nextY][nextX] > curHeight)
            {
                pq.push({ nextY,nextX,arr[nextY][nextX] });
            }
            else
            {
                answer += (long long)curHeight - arr[nextY][nextX];
                pq.push({ nextY,nextX,curHeight });
            }
        }
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> col >> row;
 
    for (int i = 0; i < row; ++i)
    {
        for (int j = 0; j < col; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    for (int i = 0; i < row; ++i)
    {
        for (int j = 0; j < col; ++j)
        {
            if (isEdge(i, j))
            {
                visited[i][j] = true;
                pq.push({ i,j,arr[i][j] });
            }
        }
    }
 
    solve();
    cout << answer;
}

 

이전에 수영장 만들기.. 라는 문제를 통해 3차원맵의 물을 채우는 문제를 풀어봤었다.

해당 풀이법으로 이 문제에 적용 시에는 시간초과가 뜬다. 맵크기도 더 커지기도 했고, 높이가 최대 10억이라서, 같은 로직을 적용하면 말도안되게 시간이 초과된다.

물을 최대높이 까지 채운 후, 한층한층씩 빼는식의 로직인데 높이가 최대 10억이라 안된다..

 

 

그래서 새로운 로직을 적용한다. 

우선순위큐를 활용하여, 제일 높이가 낮은 노드만 뽑아서 로직을 수행한다. 외각은 항상 물이 새기 때문에 외각의 노드들을 먼저 우선순위큐에 다 넣는다.

뽑은 노드의 상하좌우 방향노드에 대해 검사를 할건데, 만약 새로운 노드의 높이가 현재노드가 높다면, 해당 노드가 새로운 기준이 되야하기 때문에 해당 노드 정보 그대로 큐에 넣는다.

반대로 새로운 노드의 높이가 현재노드높이의 '이하'이면 그 차이만큼 정답에 반영한다.

 

자 여기서 새로운 노드 높이가 더 높으면 왜 새로운 기준이 되느냐?

더 높기때문에 더 많은 물을 담을 수 있을 '가능성'이 생기기 때문이다.

그러면 이런 의문이 생긴다. '어? 근데 더 높아도, 다른쪽이 낮으면은 거기가 기준 아닌가?' 

-> 그렇기 때문에 우선순위큐로 낮은높이의 노드부터 뽑는것이다.

    낮은높이에서 먼저 접근해서 정답에 카운팅해버리고 해당 좌표에 방문체크를 해버리기 때문에, 나중에 높은곳에서 접근 못하게 막을 수 있는 것이다.