[C++]백준 2468번: 안전 영역

문제

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

2468번: 안전 영역

 

문제이해

 

• 첫째 줄에 N을 입력한다.
• 두번째 줄부터 NxN 크기의  영역의 정보를 입력한다.
• 안전한 영역의 최대 개수를 출력한다.

 

구현하는게 생각보다 간단한 문제입니다. 높이를 정하고 높이에 따라 잠기지 않는 영역을 발견하면 그 옆에 붙어있는 잠기지 않는 영역까지 구하기 위해 너비우선탐색(BFS)를 사용하여 구역을 찾고 구역의 개수를 구하면 됩니다.

 

물에 잠기지 않는 안전한 영역의 최대 개수를 구하기 위해 잠기게 되는 물의 높이를 영역들중 가장 낮은 영역의 높이부터 시작해서 영역들 중 가장 높은 영역의 높이까지로 하여 위의 과정을 반복해야 합니다.

 

다음은 해당 내용대로 작성된 코드 입니다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N;
int startHeight{ 101 };
int endHeight{ 0 };
int maxCount{ 1 };
vector<vector<int>> map;

int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

void search(int height) {
	if (height >= endHeight) {
		return;
	}
	int visited[100][100] = { 0 };
	int cot{ 0 };
	for (int i{ 0 }; i < N; i++) {
		for (int a{ 0 }; a < N; a++) {
			if (map[i][a] > height && visited[i][a] == 0) {
				queue<pair<int,int>> safe;
				safe.push(make_pair(i, a));
				visited[i][a] = 1;
				while (!safe.empty()) {
					int topX = safe.front().first;
					int topY = safe.front().second;
					safe.pop();

					for (int i{ 0 }; i < 4; i++) {
						int newX = topX + dx[i];
						int newY = topY + dy[i];

						if (newX >= 0 && newX < N && newY >= 0 && newY < N && visited[newX][newY] == 0) {
							if (map[newX][newY] > height) {
								safe.push(make_pair(newX, newY));
								visited[newX][newY] = 1;
							}
						}
					}
				}
				cot++;
			}
		}
	}
	if (cot > maxCount)
		maxCount = cot;
	search(height + 1);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N;
	map.resize(N, vector<int>(N));
	for (int i{ 0 }; i < N; i++) {
		for (int a{ 0 }; a < N; a++) {
			cin >> map[i][a];
			if (map[i][a] < startHeight)
				startHeight = map[i][a];
			if (map[i][a] > endHeight)
				endHeight = map[i][a];
		}
	}
	search(startHeight);
	cout << maxCount;
}

 

재귀함수 search를 이용하여 시작 높이(영역들중 가장 낮은 높이)부터 시작하여 끝 높이(영역들중 가장 높은 높이)까지의 영역들의 개수를 구했습니다.

 

영역들의 개수중에 최댓값을 저장하고 이를 결과로 출력하였습니다.

 

문제후기

여러 알고리즘이 들어간 문제로 생각보다 어려웠습니다.