백준 2468번: 안전 영역 (C++)

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

2468번: 안전 영역

 

입력을 받으면서, 입력받는 높이의 최소와 최대를 구해둔다.

 

1부터 100까지 다 해볼 필요 없이 필요한 것만 해보는 것이다. 문제에서 아무 곳도 잠기지 않는 경우도 있다고 명시했기 때문에 높이 제한의 최소-1부터 최대까지를 물의 높이 변화로 정해주면 된다.

 

#include<iostream>
using namespace std;
int N, m[102][102];
bool vis[102][102];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
void dfs(int row, int col, int H) {
	vis[row][col] = true;
	for (int i = 0; i < 4; i++) {
		int nr = row + dr[i];
		int nc = col + dc[i];
		if (nr < 0 || nc < 0 || nr >= N || nc >= N) continue;
		if (vis[nr][nc] || m[nr][nc] <= H) continue;
		dfs(nr, nc, H);
	}
}
void init() {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			vis[i][j] = false;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	int hMin = 110, hMax = -1;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> m[i][j];
			if (m[i][j] > hMax) hMax = m[i][j];
			if (m[i][j] < hMin) hMin = m[i][j];
		}
	}
	
	int cntMax = 0;
	for (int h = hMin - 1; h <= hMax ; h++) {
		int cntH = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (m[i][j] > h && !vis[i][j]) {
					dfs(i, j, h);
					cntH++;
				}
			}
		}
	
		if (cntH > cntMax) cntMax = cntH;
		init();
	}
	cout << cntMax << '\n';
	return 0;
}