[백준 14324] Rain (Small) (C++)

문제 링크: www.acmicpc.net/problem/14324

14324번: Rain (Small)

※ 비슷한 문제: www.acmicpc.net/problem/1113

1113번: 수영장 만들기

 

1. 주의할 점

- BFS를 통해 진행하되, 외곽에서부터 접근이 가능한지 확인한다

- 매 TC마다 초기화를 수행한다

 

2. 구현

- 입력받은 정보의 외곽을 0으로 한번 둘러싸는 형태를 지니도록 한다

- 최고 지점을 Maxi에 저장하고, 1부터 Maxi까지 비가 차오르도록 하여 늘어난 양을 계산한다

- BFS(int val)를 통해 외곽에서부터 시작하여 빗물이 차오르도록 하며, 만약 외곽에서 접근할 수 있는, Val보다 낮은 지형은 Val로 변환한다

- BFS(int val)를 마친 이후, 외곽에선 접근할 수 없으나 val보다 낮은 높이만큼 차있다면 해당 높이를 val로 바꾸고, Result++한다(둘의 최대 차이는 1이기 때문) 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct info {
	int x, y;
};
info tmp;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int arr[12][12];
int row, col, result;

void bfs(int val) {
	queue<info> q;
	tmp.x = 0;
	tmp.y = 0;
	q.push(tmp);
	while (!q.empty()) {
		int cx = q.front().x;
		int cy = q.front().y;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			if (nx >= 0 && ny >= 0 && nx <= col + 1 && ny <= row + 1 && arr[ny][nx] < val) {
				arr[ny][nx] = val;
				tmp.x = nx;
				tmp.y = ny;
				q.push(tmp);
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int test, maxi;
	cin >> test;
	for (int t = 0; t < test; t++) {
		//초기화
		result = 0;
		for (int i = 0; i < 12; i++)
			for (int j = 0; j < 12; j++)
				arr[i][j] = 0;
		maxi = 0;

		cin >> row >> col;
		for (int i = 1; i <= row; i++)
			for (int j = 1; j <= col; j++) {
				cin >> arr[i][j];
				maxi = max(maxi, arr[i][j]);
			}
		for (int k = 1; k <= maxi; k++) {
			bfs(k);
			for (int i = 1; i <= row; i++)
				for (int j = 1; j <= col; j++) {
					if (arr[i][j] < k) {
						arr[i][j] = k;
						result++;
					}
				}
		}
		cout << "Case #" << t + 1 << ": " << result << '\n';
	}
	return 0;
}