빗물

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	10664	5888	4659	55.770%

문제

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

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

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력

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

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

예제 입력 1

4 4
3 0 1 4

예제 출력 1

5

예제 입력 2

4 8
3 1 2 3 4 1 1 2

예제 출력 2

5

예제 입력 3

3 5
0 0 0 2 0

예제 출력 3

0

출처

University > 충남대학교 > 생각하는 프로그래밍 대회  D번

• 문제를 만든 사람: isku

알고리즘 분류

• 구현
• 시뮬레이션

---

아래서부터 블록과 블록 사이에 공간을 카운트하여 고여있는 빗물의 칸을 계산할 생각

좌/우 를 확인하면서 빈공간을 체크하면 좋을 것 같다.

입력 확인 코드

#include <iostream>

using namespace std;

// 가로, 세로의 길이는 최대치가 500
constexpr auto MAX = 500;

// 0 빈공간, 1 블록
int map[MAX][MAX];

// 가로 / 세로
int H, W, tempOne, tempTwo;

// 빗물의 개수
int rainwaterCnt = 0;

bool debugbool = true;

// 시각적인 디버깅을 위한 함수
void VisualDebug()
{
	cout << "\n";
	for (int i = 0; i < W; i++)
	{
		for (int j = 0; j < H; j++)
		{
			cout << map[i][j] << " ";
		}
		cout << "\n";
	}
}

// 문제의 입력을 받는 함수
void ReceiveInput()
{
	cin >> H >> W;

	tempTwo = W;

	for (int i = 0; i < tempTwo; i++)
	{
		cin >> tempOne;
		for (int j = 0; j < tempOne; j++)
		{
			map[i][j] = 1;
		}
	}
	
}

// 초기화를 진행하는 함수
void Initialization()
{
	for (int i = 0; i < MAX; i++)
	{
		for (int j = 0; j < MAX; j++)
		{
			map[i][j] = 0;
		}
	}
}

int main()
{
	Initialization();
	ReceiveInput();
	if (debugbool) { VisualDebug(); }

	return 0;
}

문제의 힌트와 배열이 다른 것에 주의

통과된 코드

#include <iostream>

using namespace std;

// 가로, 세로의 길이는 최대치가 500
constexpr auto MAX = 500;

// 0 빈공간, 1 블록
int map[MAX][MAX];

// 가로 / 세로
int H, W, tempOne;

// 첫 블록을 마킹하는 bool 값
bool leftRight;

// 빗물의 개수
int rainwaterCnt;

bool debugbool = false;

// 시각적인 디버깅을 위한 함수
void VisualDebug()
{
	cout << "\n";
	for (int i = 0; i < W; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			cout << map[i][j] << " ";
		}
		cout << "\n";
	}
}

// 문제의 입력을 받는 함수
void ReceiveInput()
{
	cin >> H >> W;

	for (int i = 0; i < W; i++)
	{
		cin >> tempOne;
		for (int j = 0; j < tempOne; j++)
		{
			map[i][j] = 1;
		}
	}
}

// 초기화를 진행하는 함수
void Initialization()
{
	for (int i = 0; i < MAX; i++)
	{
		for (int j = 0; j < MAX; j++)
		{
			map[i][j] = 0;
		}
	}
}

// 빗물을 카운트 합니다.
void CountRainwater()
{
	rainwaterCnt = 0;

	// 아래부터 위로 검색
	for (int i = 0; i < H; i++)
	{
		leftRight = false;
		tempOne = 0;

		for (int j = 0; j < W; j++)
		{
			if (map[j][i] == 1)
			{
				if (!leftRight)
				{
					// 좌에서 우로 검색하다 처음 블록을 찾으면 마킹
					leftRight = true;
					tempOne = 0;
				}
				else
				{
					// 마킹이 되어있는 상태에서 블록을 찾으면 
					// 빈공간을 카운트하는 tempOne을 결과값에 더해준다.
					// 그리고 0으로 초기화
					rainwaterCnt += tempOne;
					tempOne = 0;
				}

			}
			else if (map[j][i] == 0)
			{
				// 해당 위치가 빈공간이고 첫 블록 마킹이 되어있다면 
				// 빈공간을 카운트하는 tempOne을 하나 늘려줍니다.
				if (leftRight)
				{
					tempOne++;
				}

			}
		}
	}
}

int main()
{
	Initialization();
	ReceiveInput();
	CountRainwater();
	if (debugbool) { VisualDebug(); }
	// 결과를 출력합니다.
	cout << rainwaterCnt;
	return 0;
}

처음에 생각한 간단한 로직으로 코드를 구현하고 통과한 문제입니다.

이 문제를 해결하는 방법은 다양할 것 같습니다.