[2468] 안전 영역, c++

[2468] 안전 영역

 

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

2468번: 안전 영역

전형적인 그래프 문제

그냥 기준 높이를 다 돌려봐서 최대 출력하면 된다. 시간초과 날까 약간 고민했는데 테스트 수가 적어서 그런지 안남.

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int arr[101][101];
int cnt[101]={0};
int n;
bool check[101][101]={false};
void dfs(int x, int y, int rain){
	check[x][y] = true;
	if(x+1<n && x+1>=0 && check[x+1][y] == false && arr[x+1][y] > rain){
		dfs(x+1,y,rain);
	}
	if(x-1>=0 && x-1<n && check[x-1][y] == false && arr[x-1][y] > rain){
		dfs(x-1,y,rain);
	}
	if(y+1<n && y+1>=0 && check[x][y+1] == false && arr[x][y+1] > rain){
		dfs(x,y+1,rain);
	}
	if(y-1 >= 0 && y-1 < n && check[x][y-1] == false && arr[x][y-1] > rain){
		dfs(x,y-1,rain);
	}
}
int main(){
	cin >> n;
	int s=200,m=0;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			scanf("%d", &arr[i][j]);
			s=min(arr[i][j], s);
			m=max(arr[i][j], m);
		}
	}
	int max2=0;
	for(int k=s; k<=m; k++){
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(check[i][j] == false && arr[i][j]>k){
					dfs(i,j,k);
					cnt[k]++;
				}
			}
		}
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				check[i][j] = false;
			}
		}
		max2 = max(cnt[k],max2);
	}
	if(max2 == 0)	printf("1");
	else{
		printf("%d",max2);
	}
}

풀이) 처음에 입력 받을 때 max 높이와 min 높이를 찾아 놓는다.

그 후 min~max 까지 dfs 를 통해 기준 높이보다 높은 곳을 방문한다. 방문하다 끊기는 순간->안전영역-> cnt 개수 증가

이 때, 아무 지역도 물에 잠기지 않는다 이 말이 중요한데 즉, 비가 안 올 수도 있는 경우 이 경우 모든 높이가 동일하면 안전영역은 1개밖에 나오지 않음. 그러므로 max2 값이 0인경우를 1로 바꿔 출력해야한다.

이 문제는 테스트 케이스, 예외 케이스 모두 정답이 출력 됐는데 계속 틀렸습니다가 떴다 알고보니 memset을 잘못 써서..