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

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

14719번: 빗물

 

아이디어만 떠오르면 굉장히 쉬운 문제다. 다행히도 문제를 읽고 생각나는대로 알고리즘을 짜봤는데 잘 맞아서 빨리 풀 수 있었다. 아이디어는 아래와 같다.

​

모든 칸에 대해 '흰색'이면 그 칸을 기준으로 같은 행에 좌우로 검은색 칸이 있으면 그 칸은 빗물이 고이는 칸이다. 사실 이게 끝이다. 더 설명할게 없다. 나는 아래와 같은 순서로 코드를 구현했다.

​

1. 2차원 배열을 0으로 초기화. 즉 0이 흰칸.

2. 검은칸을 1로 초기화. 즉 1이 검은칸.

3. 모든 칸에 대해 흰칸이면 좌우에 검은칸이 있는지 검사하고 있으면 정답에 1 더해준다.

4. 정답 출력

 

#include <iostream>
using namespace std;

int main() {

	int row, col;
	cin >> row >> col;
	
	int** map = new int*[row];
	for (int i = 0; i < row; i++)
		map[i] = new int[col];

	// 1. 흰색 0으로 칠하기
	for (int i = 0; i < row; i++) 
		for (int j = 0; j < col; j++) 
			map[i][j] = 0;

	// 2. 검은색 1로 칠하기
	int tmp;
	for (int c = 0; c < col; c++) {
		cin >> tmp;

		// 아래부터 높이만큼 색칠(열 고정)
		for (int r = row - 1; r >= row - tmp; r--) {
			map[r][c] = 1;
		}
	}

	int ans = 0;
	int check; // 좌우에 검은색 있는지 확인용
	// 3. 흰색이면 좌우 끝에 검은색 있으면 ans++
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			if (map[i][j] == 0) {
				// 행 고정, 열만 j 기준 좌우로 움직인다
				check = 0;

				// 1) 좌로 먼저
				tmp = j;
				while (tmp >= 0) {
					if (map[i][tmp] == 1) {
						check++;
						break;
					}
					tmp--;
				}

				// 2) 우로
				tmp = j;
				while (tmp < col) {
					if (map[i][tmp] == 1) {
						check++;
						break;
					}
					tmp++;
				}

				// check == 2면 ans++
				if (check == 2) ans++;
			}
		}
	}

	cout << ans << endl;

    // 할당해제
    for(int i = 0; i < row; i++) { 
        delete[] map[i]; 
    } 
    delete[] map;

	return 0;
}