알고리즘 :: 백준 :: 2468 - 안전 영역

 

 

 

 

 

 

 

❔문제

🔗문제링크

 

🔄 문제 및 입출력 조건 파악

• N × N 크기의 맵, 2 ≤ N ≤ 100
• 각 칸마다 1 ≤ 높이≤ 100
• 아무 지역도 물에 잠기지 않을 수도 있다.

✏️ 문제풀이

문제에 나와있지 않은 조건을 당연히 그럴거라 추측하고 풀면 안 된다는걸 연습하기 좋은 문제입니다.

• 물의 높이를 당연히 1부터 시작할거라 생각했다면, 당한겁니다.
• 문제 어디에도 '비가 무조건 내려야 한다'는 말이 없기 때문에, 일단 0부터 시작해야 합니다.

물의 높이는 0부터 시작해서 입력받은 N × N 칸의 높이 중 가장 큰 높이까지 (또는 그냥 100까지)를 검사하면 됩니다.

 

검사는 다음과 같은 과정으로 이뤄집니다.

1. '물에 잠기지 않은 임의의 칸'(즉, `arr[y][x] > 물의 높이`) 부터 시작.
2. 현재 물에 잠기지 않았고, 연결돼있어서 방문할 수 있는 (즉, DFS 또는 BFS 1회로 갈 수 있는 곳들) 모든 칸을 방문표시.
3. 다른 칸들 순회하며 또 2번을 수행할 수 있는 칸 찾아보기.
4. 모든 칸을 순회했을 때, DFS 또는 BFS를 몇 번 수행했는지 확인하기.

요약하면, 물의 높이를 변경해가면서 connected component가 몇 개인지 반복해서 확인하고, 그 최댓값을 구하는 문제입니다.

 

📝 코드

#include <bits/stdc++.h>
using namespace std;

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

int N;
bool visited[101][101];
array<array<int, 101>, 101> arr;

inline bool isNotValid(int y, int x) {
	return (y < 0) || (x < 0) || (y >= N) || (x >= N);
}

void dfs(int y, int x, int h) {
	visited[y][x] = true;
	for (int i = 0; i < 4; ++i) {
		int ny = y + dy[i], nx = x + dx[i];
		if (isNotValid(ny, nx) || visited[ny][nx] != 0 || arr[ny][nx] <= h) continue;
		dfs(ny, nx, h);
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	
	cin >> N;
	int maxHeight = 0;
	for (int y = 0; y < N; ++y) {
		for (int x = 0; x < N; ++x) {
			cin >> arr[y][x];
			maxHeight = max(maxHeight, arr[y][x]);
		}
	}
	int result = 1;
	for (int h = 1; h <= maxHeight; ++h) {
        fill(begin(visited)->begin(), visited.back().end(), 0);
		int safeCnt = 0;
		for (int y = 0; y < N; ++y) {
			for (int x = 0; x < N; ++x) {
				if (visited[y][x] == false && arr[y][x] > h) {
					dfs(y, x, h);
					safeCnt++;
				}
			}
		}
		result = max(result, safeCnt);
	}
	cout << result;
}

 

🔗 코드 링크

🕧 결과