백준 15972 - 물탱크(C++)

문제 링크입니다. https://www.acmicpc.net/problem/15972

15972번: 물탱크

우선순위 큐와 그래프를 이용해 푸는 문제입니다.

개념이 복잡하고 구현이 어려웠던 문제입니다.

문제를 풀기 전에 구역에서 구멍을 표시하는 방법부터 정해야 합니다.

한 구역에서 구멍을 가질 수 있는 방법은 4가지 입니다. -> 상하좌우

해당 그림과 같이 상하좌우를 표시합니다. 

 

탱크 속 물이 바뀌는 방법입니다. 

1. 구멍에 높이에 맞춰서 높이가 조절

2. 구멍의 높이와 별개로 연결된 물탱크의 높이에 맞춰 높이가 조절

 

문제 접근 방법

1. 처음에는 바깥면에 있는 구멍을 통해서만 물을 뺀다.

   1-1. 물이 빠졌으면 바뀐 높이와 해당 좌표를 우선순위 큐에 넣어준다.

2. 큐에 넣어진 데이터를 통해서 해당 좌표에서 상하좌우를 확인한다.

   2-1. 데이터의 좌표에서 물의 높이와 실제 물의 높이가 다르다면 넘어간다.

   2-2. 상하좌우 중, 구멍이 있는 부분만 탐색한다.

3. 다음 좌표 값에서 바뀔 물의 양은 max(min(hole[x][y][i], tank[xx][yy]), tank[x][y]) 입니다.

4. 1~3 과정을 계속 반복합니다.

 

문제 접근 방법 1

다음 그림과 같습니다.

상하좌우의 다음 칸들을 확인해서 물을 빼줍니다.

 

 

문제 접근 방법 3

해당 과정은 현재 물탱크 좌표의 높이를 바꾸는 것이 아닌 다음 물탱크의 높이를 바꾸는 과정입니다.

따라서 바뀌는 경우는

1. 다음 좌표의 물탱크 물의 양이 연결된 구멍보다 높고 현재 물탱크 물의 양이 다음 물탱크의 물의 양보다 작을때

   -> 현재 물탱크의 양으로 맞춰진다.

2.  다음 좌표의 물탱크 물의 양이 연결된 구멍보다 높고 현재 물탱크 물의 양이 연결된 구멍보다 작을 때

   -> 구멍의 높이로 맞춰진다.

이외의 경우는 전부 drain_water() 함수에서 바로 return됩니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstring>
#include <string>
#define INF 987654321
#define P pair<int,int>
#define PP pair<int, P>
using namespace std;


int N, M, H;
priority_queue<PP, vector<PP>, greater<PP>> q;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int hole[1003][1003][4];
int tank[1003][1003];

void drain_water(int x, int y, int mass) {
	if (tank[x][y] <= mass) return;
	tank[x][y] = mass;
	q.push({ mass,{x,y} });
}

void drain_outside_water() {
	//상하의 바깥면에 있는 물을 먼저 뺀다
	for (int i = 0; i <= M + 1; i++) {
		if (hole[0][i][2] != -1) {
			drain_water(1, i, hole[0][i][2]);
		}
		if (hole[N + 1][i][0] != -1) {
			drain_water(N, i, hole[N + 1][i][0]);
		}
	}
	//좌우의 바깥면에 있는 물을 먼저 뺀다
	for (int i = 0; i <= N + 1; i++) {
		if (hole[i][0][1] != -1) {
			drain_water(i, 1, hole[i][0][1]);
		}
		if (hole[i][M + 1][3] != -1) {
			drain_water(i, M, hole[i][M+1][3]);
		}
	}
}

void BFS() {
	while (!q.empty()) {
		int water = q.top().first;
		int x = q.top().second.first;
		int y = q.top().second.second;
		q.pop();
		//이미 탱크의 물이 바뀌었다면 확인할 필요가 없다.
		if (tank[x][y] != water) continue;
		for (int i = 0; i < 4; i++) {
			//확인하려고 하는 방향에 구멍이 없는 경우면 확인할 필요가 없다.
			if (hole[x][y][i] == -1) continue;
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && xx <= N && yy >= 1 && yy <= M) {
				int next_water = max(min(hole[x][y][i], tank[xx][yy]), tank[x][y]);
				drain_water(xx, yy, next_water);
			}
		}
	}
}

void solve() {
	int ans = 0;
	drain_outside_water();
	BFS();
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			ans += tank[i][j];
		}
	}
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> H;
	/// 상하 구멍
	for (int i = 1; i <= N + 1; i++) {
		for (int j = 1; j <= M; j++) {
			int x;
			cin >> x;
			hole[i][j][0] = x;
			hole[i - 1][j][2] = x;
		}
	}
	///  좌우 구멍
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M + 1; j++) {
			int x;
			cin >> x;
			hole[i][j][3] = x;
			hole[i][j - 1][1] = x;
		}
	}
	/// 처음에는 물을 가득 채운다
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			tank[i][j] = H;
		}
	}
	solve();
	return 0;
}

 

질문 및 조언은 댓글 남겨주세요