[BOJ/백준 14719/C++] 빗물

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

14719번: 빗물

 

[문제 요약]

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

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

 

[문제 조건]

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

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

- 시간 제한 : 1초

- 메모리 제한 : 256MB

 

[문제 풀이]

빗물이 고인다는 것은 높은 기둥 사이에 갇힌 공간이 있을 때 빗물이 고이게 된다.

 

따라서 주어진 블록들의 높이를 하나씩 확인하면서 왼쪽의 가장 높은 기둥, 오른쪽의 가장 높은 기둥을 찾아 높이 차이를 구해 고이게 되는 빗물의 양을 구해서 모두 더하는 방법이 있다.

 

하지만 필자는 다르게 접근했다. 물론 이 방법이 조건을 다르게하면 메모리 문제가 생길 순 있다.

 

필자가 사용한 방법은 그냥 주어진 정보들을 2차원 배열로 만들어서 고이게 되는 빗물의 양을 다 구했다.

 

배열에 주어진 정보들을 저장하고 H-1번째 행부터 0번째 행까지 거꾸로 확인하면서 고이게될 공간의 갯수를 세었다.

현재 위치에 물이 고일지 안고일지 판별하는 조건은 다음과 같다.

• 이전 배열의 값이 1이고 현재 값이 0이면 flag라는 변수를 true로 바꿔주고 cnt값을 하나 증가시킨다.
• flag의 값이 true고 현재 배열의 값이 1이면 flag를 false로 바꾼 뒤 cnt를 ans 값에 추가한다 ( ans+=cnt ) 그리고 cnt=0으로 초기화
• flag의 값이 true고 현재 배열의 값이 0이면 cnt값 증가

위의 조건들을 그림으로 나타내면

예제에서 주어진 것과 같이 파란색 부분을 찾는 것이다.

 

1과 1사이의 0의 갯수를 세어서 ans에 더해 준다고 생각하면 쉽다.

 

[소스 코드]

 

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <list>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

#define pii pair<int,int>

using namespace std;

int W, H;

vector<vector<int>> mp;
vector<int> dt;

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

	cin >> H >> W;
	dt.resize(W);
	mp.resize(H);
	for (int i = 0; i < H; i++) mp[i].resize(W);

	for (int i = 0; i < W; i++) cin >> dt[i];

	for (int j = 0; j < W; j++)
	{
		for (int i = H - 1; i > H - 1 - dt[j]; i--) mp[i][j] = 1;
	}

	int ans = 0;
	bool flag = false;
	for (int i = H - 1; i >= 0; i--)
	{
		flag = false;
		int prev = 0;
		int cnt = 0;
		for (int j = 0; j < W; j++)
		{
			if (mp[i][j] == 0 && prev == 1) { flag = true; cnt++;}
			else if (flag && mp[i][j] == 1) { flag = false; ans += cnt; cnt = 0; }
			else if (flag && mp[i][j] == 0) { cnt++; }
			prev = mp[i][j];
		}
	}
	cout << ans;
}

굳