[백준/BOJ] 백준 15972번 : 물탱크

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

15972번: 물탱크

 

바깥쪽 벽에 구멍이 있을 때 물이 빠지는 것과 구멍의 높이가 낮은 게 물이 많이 빠지는 것을 고려하여 바깥쪽부터 시작하여 구멍의 높이가 낮은 것부터 인접한 방향에 구멍으로 연결되어 인접한 방향의 구역이 물이 빠지는 것을 이용하여 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

int n, m, h;
int board[1000][1000][4]; //[x좌표][y좌표][0:왼쪽, 1:위쪽, 2:오른쪽, 3:아랫쪽 벽(구멍이 위치할 수 있는 곳)]
priority_queue<tuple<int, int, int>> pq;//(-구멍의 높이, x좌표, y좌표)
vector<vector<int>> result(1000, vector<int>(1000, 987654321)); //각 칸에 남게되는 물의 양
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m >> h;

	for (int i = 0; i < n + 1; i++)
	{
		for (int j = 0; j < m; j++)
		{
			int this_h;
			cin >> this_h;

			if (i != n)
				board[i][j][1] = this_h;

			if (i != 0)
				board[i - 1][j][3] = this_h;
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m + 1; j++)
		{
			int this_h;
			cin >> this_h;

			if (j != m)
				board[i][j][0] = this_h;

			if (j != 0)
				board[i][j - 1][2] = this_h;
		}
	}

	//바깥쪽에 구멍이 있는것을 모두 우선순위큐에 넣는다
	for (int j = 0; j < m; j++)
	{
		if (board[0][j][1] != -1)
		{
			pq.push(make_tuple(-board[0][j][1], 0, j));
			result[0][j] = min(result[0][j], board[0][j][1]);
		}

		if (board[n - 1][j][3] != -1)
		{
			pq.push(make_tuple(-board[n - 1][j][3], n - 1, j));
			result[n - 1][j] = min(result[n - 1][j], board[n - 1][j][3]);
		}
	}
	for (int i = 0; i < n; i++)
	{
		if (board[i][0][0] != -1)
		{
			pq.push(make_tuple(-board[i][0][0], i, 0));
			result[i][0] = min(result[i][0], board[i][0][0]);
		}

		if (board[i][m - 1][2] != -1)
		{
			pq.push(make_tuple(-board[i][m - 1][2], i, m - 1));
			result[i][m - 1] = min(result[i][m - 1], board[i][m - 1][2]);
		}
	}

	while (!pq.empty())
	{
		int here_height = -get<0>(pq.top());
		pair<int, int> here = make_pair(get<1>(pq.top()), get<2>(pq.top()));
		pq.pop();

		if (here_height > result[here.first][here.second])
			continue;

		//해당 칸과 인접한 칸들 확인
		for (int i = 0; i < 4; i++)
		{
			//해당 방향쪽으로 구멍이 나있지 않을때
			if (board[here.first][here.second][i] == -1)
				continue;

			pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

			if (there.first < 0 || there.first >= n || there.second < 0 || there.second >= m)
				continue;

			//구멍의 높이와 there의 물의 높이중 작은것을 고른다
			int there_min = min(board[here.first][here.second][i], result[there.first][there.second]);

			//here위치의 높이와 there_min중 큰것을 고른다
			int there_check = max(here_height, there_min);

			if (result[there.first][there.second] > there_check)
			{
				result[there.first][there.second] = there_check;
				pq.push(make_tuple(-there_check, there.first, there.second));
			}

		}
	}

	int output = 0;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (result[i][j] == 987654321)
				output += h;
			else
				output += result[i][j];
		}
	}

	cout << output;

	return 0;
}