백준2468 - 안전 영역

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

2468번: 안전 영역

비가 올 때 잠기지 않을 지대의 갯수를 세주면 된다. 영역의 넓이를 구하기 위하여 dfs를 사용하였다. 주의할 것은 비가 아예 오지 않을 수도 있기 때문에 0을 반드시 넣어주어야 한다. 비는 현재 입력한 지대의 높이로만 온다고 설정하였다. 왜냐하면 3과 5인 지점이 있고 4인 지점이 없다고 가정하면 3인 지점은 3, 4, 5 모두 비가 오면 잠긴다. 4에 잠기는 지점은 5가 와도 잠기니까 4는 결과적으로 찾지 않아도 된다.

 

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

int cnt; //영역의 갯수
int N; //영역의 높이
int mat[101][101]; //땅의 정보
bool visit[101][101]; //방문 정보

//동서남북으로 1만큼 이동
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };

int check;//현재 비교할 비의 높이
int ans; //답

set<int> st; //비가 올 수 있는 높이
set<int>::iterator iter; //set의 iterator

//dfs
void dfs(int x, int y) {
	visit[x][y] = true; //현재 위치 방문
	for (int i = 0; i < 4; i++) { //동서남북 4방향
		//이동한 결과
		int nx = x + dx[i];
		int ny = y + dy[i];

		//범위 안에 있고 방문을 안 했으며 현재 비의 높이보다 높은 지대이면
		if (1 <= nx && nx <= N && 1 <= ny && ny <= N && mat[nx] && !visit[nx][ny] && mat[nx][ny] > check) {
			dfs(nx, ny); //dfs 수행
		}
	}
}

int main() {
	cin >> N; //땅의 길이 설정

	st.insert(0); //비가 안 올 수도 있어서 0을 넣는다.

	//땅에 대한 정보와 비의 높이를 넣는다.
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> mat[i][j];
			st.insert(mat[i][j]);
		}
	}
	
	//비의 높이를 기준으로 차례대로 잠기지 않을 지대의 갯수를 센다.
	for (iter = st.begin(); iter != st.end(); iter++) {
		check = *iter;
		cnt = 0;
		
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (!visit[i][j] && mat[i][j] > check) { //방문을 안했고 현재 지대가 안 잠기는 지대이면
					dfs(i, j); //탐색 수행
					cnt++; //잠기지 않는 지대의 갯수 증가
				}
			}
		}
		
		//visit을 false로 초기화
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				visit[i][j] = false;
			}
		}

		ans = max(ans, cnt); //답을 갱신
	}

	cout << ans;
}