[C++][백준] 빗물(14719)

문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

 

출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

 

풀이

자료구조 스택을 사용하여 문제를 풀이하였습니다.

 

기준이 되는 기둥을 시작으로 기준 기둥보다 높이가 같거나 높은 기둥이 등장했을 때 빗물을 계산할 수 있습니다. 

기준 기둥의 위치를 first_idx, 높이를 first_block에 저장하였습니다. 

 

기준 기둥보다 높이가 같거나 높은 기둥이 아니라면 stack에 저장하고 

기준 기둥보다 높이가 같거나 높은 기둥이 등장했을 때 stack에 저장한 기둥들을 pop하며 계산해나갑니다.

 

계산 대상이 되는 가장 왼쪽 기둥(기준 기둥)의 높이 <= 가장 오른쪽 기둥의 높이기 때문에

(왼쪽 기둥 - 기둥 높이)가 고인 빗물의 양이 됩니다.

 

그러나 해당 로직은 마지막에 아래와 같은 상황이 발생했을 때를 커버하지 못합니다.

이 경우 스택에 기준 기둥으로부터 마지막 기둥까지 정보가 남아있습니다.

스택에 값이 남아있지 않은 위와 같은 상황에서는 반대로 오른쪽부터 값을 계산해갑니다.

 

이때는 반대로 가장 오른쪽 기둥을 기준 기둥으로 설정합니다.

기준 기둥으로부터 왼쪽을 살펴보며 기준 기둥보다 높이가 낮으면 빗물을 계산해주고(기준 기둥 높이 - 기둥 높이)

기준 기둥보다 높이가 높으면 기준 기둥을 change 해줍니다.

 

전체 코드는 아래와 같습니다.

#include <iostream>
#include <stack>

using namespace std;

int H, W;
int blocks[510];

struct myData {
	int height;
	int idx;
};

stack<myData> myStack;

int main() {
	int ans = 0;
	cin >> H >> W;

	for (int i = 0; i < W; i++) {
		cin >> blocks[i];
	}

	int first_block;
	int first_idx;
	for (int i = 0; i < W; i++) {
		int block = blocks[i];
		if (i == 0) {
			myStack.push({ block, i });
			first_block = block;
			first_idx = i;
		}
		else {
			 if (first_block <= block) { // 계산 가능
				 while (!myStack.empty()) {
					 int curBlock = myStack.top().height;
					 int curIdx = myStack.top().idx;
					 myStack.pop();

					 if (curIdx == first_idx) break;
					 ans += first_block - curBlock;
				 }
				 first_block = block;
				 first_idx = i;
			 }
			 myStack.push({ block, i });
		}
	}

	if (!myStack.empty()) {
		int base_block = myStack.top().height;
		while (!myStack.empty()) {
			int curBlock = myStack.top().height;
			int curIdx = myStack.top().idx;
			myStack.pop();

			if (curIdx == first_idx) break;
			if (curBlock < base_block) {
				ans += base_block - curBlock;
			}
			else if (curBlock > base_block) {
				base_block = curBlock;
			}
		}
	}

	cout << ans;

	return 0;
}