C++ / 백준 / 2468 / 안전 영역

문제

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

2468번: 안전 영역

문제풀이

DFS로 문제를 풀었다.

비 오면 잠기는 높이를 0부터 설정하여 최대 높이-1까지 반복한다.

벡터 범위 안을 돌면서 물에 잠기지 않은 지역을 발견하면 큐에 push를 하고 queue가 빌 때까지 상하좌우를 살핀다.

땅이 잠기지 않았고 방문을 한 적이 없으면 방문하고 큐에 push 한다.

큐가 비면 안전 영역의 개수를 하나 늘린다.

벡터 범위 안을 다 돌았으면 비 오면 잠기는 높이를 1 높이고 다시 반복한다.

 

vector<vector<int>>loc = { {-1,0},{1,0},{0,-1},{0,1} };
vector<vector<int>>land;
vector <vector<bool>>visit;
int y, x;
int N;
int max_high;
int max_safetyzone;

loc은 상하좌우 이동 칸 벡터,

land는 2차원 배열로 땅의 높이를 나타내는 벡터,

visit은 2차원 배열로 방문 여부를 나타내는 벡터,

max_high는 가장 높은 땅의 높이 변수,

max_safetyzone은 가장 많은 안전 영역의 개수를 저장하는 변수이다.

 

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N;
	land = vector<vector<int>>(N, vector<int>(N, 0));
	visit = vector<vector<bool>>(N, vector<bool>(N, false));

	for (y = 0; y < N; ++y) {
		for (x = 0; x < N; ++x) {
			cin >> land[y][x];
			max_high = max(max_high, land[y][x]);
		}
	}
	Rain();

	cout << max_safetyzone << "\n";
}

메인 문에서는 입력만 받고 DFS함수인 Rain함수를 실행한다.

Rain함수가 종료되면 가장 많은 안전 영역의 개수를 출력한다.

 

	int water = 0;
	queue<pair<int, int>>up;

water은 현재 물의 높이를 나타내는 변수이다.

up은 큐로 pair을 저장하는 형태로 선언한다.

up(y좌표, x좌표)를 나타낸다.

 

while (max_high--) {
		safetyzone = 0;
		fill(visit.begin(), visit.end(), vector<bool>(N, false));

가장 높은 높이수만큼 반복한다.

비의 높이가 1 증가할 때마다 안전영역을 0으로 초기화하고 방문 벡터 visit도 초기화한다.

 

for (y = 0; y < N; ++y) {
	for (x = 0; x < N; ++x) {
		if (land[y][x] > water && !visit[y][x]) {
			visit[y][x] = true;
			up.push({ y,x });
			while (!up.empty()) {
				for (int cnt = 0; cnt < 4; ++cnt) {
					int next_y = up.front().first + loc[cnt][0];
					int next_x = up.front().second + loc[cnt][1];
					if (next_y >= 0 && next_y < N && next_x >= 0 && next_x < N) {
						if (land[next_y][next_x] > water && !visit[next_y][next_x]) {
							visit[next_y][next_x] = true;
							up.push({ next_y,next_x });
						}
					}
				}
				up.pop();
			}
			safetyzone++;
		}
	}
}

코드가 길긴 한데 작동은 간단하다.

먼저 벡터 범위만큼 돌면서 현재 밟은 땅이 물에 잠기지 않고 방문하지 않았을 때 up에 y좌표, x좌표를 push 한다.

그다음 인접한 칸 (상하좌우)이 물에 잠기지 않았고, 방문하지 않았으면 up에 좌표를 push 한다.

4방향을 살펴봤으면 pop을 한다.

물에 잠기지 않은 모든 인접한 땅을 밟았으면, 안전 영역수를 1 늘린다.

벡터 범위를 모두 돌았으면 반복문이 종료된다.

 

		if (safetyzone >= max_safetyzone)
			max_safetyzone = safetyzone;
		water++;

벡터 범위를 모두 돌았으므로 비 높이가 정해졌을 때 안전 영역의 개수를 알 수 있다.

그 값이 현재 저장된 가장 많은 안전 영역 수보다 크면 값을 바꾸고 물의 높이를 1 증가시킨다.

땅의 최고 높이만큼 반복이 끝났으면 Rain함수를 종료하고 메인 문으로 돌아가 가장 많은 안전 영역수를 출력한다.

 

 

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>>loc = { {-1,0},{1,0},{0,-1},{0,1} };
vector<vector<int>>land;
vector <vector<bool>>visit;
int y, x;
int N;
int max_high;
int max_safetyzone;

void Rain() {
	int water = 0;
	int safetyzone = 0;
	queue<pair<int, int>>up;
	while (max_high--) {
		safetyzone = 0;
		fill(visit.begin(), visit.end(), vector<bool>(N, false));
		for (y = 0; y < N; ++y) {
			for (x = 0; x < N; ++x) {
				if (land[y][x] > water && !visit[y][x]) {
					visit[y][x] = true;
					up.push({ y,x });
					while (!up.empty()) {
						for (int cnt = 0; cnt < 4; ++cnt) {
							int next_y = up.front().first + loc[cnt][0];
							int next_x = up.front().second + loc[cnt][1];
							if (next_y >= 0 && next_y < N && next_x >= 0 && next_x < N) {
								if (land[next_y][next_x] > water && !visit[next_y][next_x]) {
									visit[next_y][next_x] = true;
									up.push({ next_y,next_x });
								}
							}
						}
						up.pop();
					}
					safetyzone++;
				}
			}
		}
		if (safetyzone >= max_safetyzone)
			max_safetyzone = safetyzone;
		water++;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N;
	land = vector<vector<int>>(N, vector<int>(N, 0));
	visit = vector<vector<bool>>(N, vector<bool>(N, false));

	for (y = 0; y < N; ++y) {
		for (x = 0; x < N; ++x) {
			cin >> land[y][x];
			max_high = max(max_high, land[y][x]);
		}
	}
	Rain();

	cout << max_safetyzone << "\n";
}