[2468]안전 영역(C++)

1. 문제

www.acmicpc.net/problem/2468

2468번: 안전 영역

2. 접근 방법

1) 물에 잠기는 기준 값을 standard라고 하면, standard는 1~101까지 존재한다. 

 

2) 각 standard기준보다 높이가 높아서 물에 안잠겼으면서 방문했던 적이 없었던 지역을 기준으로  dfs를 수행하여 방문처리를 한다.

 

3) standard별 그룹 수가 나오는데, 가장 큰 수를 출력한다.

 

 

3. 실수했던 부분 & 처음 알았던 부분

1) 나는 처음에 물에 잠기는 범위를 지역 높이의 최솟값~지역 높이의 최댓값이라고 생각했는데, 이렇게 구하면 안되고 모든 범위(1~101)까지에 대해서 구해야 한다.

 

2) result의 초기값을 처음에 0으로 했었는데, 이렇게 하면 비가 안올 때(K= 0) 그룹 수가 0이 된다는 의미이다. 비가 안 올 때 그룹 수는 1이므로 result = 1; 로 초기값을 주어야 한다.

 

4. 코드

#include<iostream>
#include<vector>
#include<algorithm>
#define MAX 101
using namespace std;

pair<int,int> dir[4] = {{-1,0},{0,1},{1,0},{0,-1}};

int N,standard; 
int map[MAX][MAX];
bool visited[MAX][MAX];

void dfs(int x,int y) {
	visited[x][y] = true;
	for(int i=0;i<4;i++) {
		int nx = x + dir[i].first;
		int ny = y + dir[i].second;
		if( nx < 0 || nx >= N || ny <0 || ny >= N || visited[nx][ny] ) continue;
		if( map[nx][ny] > standard ) dfs(nx,ny);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);

	int result = 1;
	cin >> N;

	for(int i =0;i<N;i++) 
		for(int j=0;j<N;j++) 
			cin >> map[i][j];
	
	//dfs 시작
	for(int k= 1; k<=101; k++) {
	 //초기화 
		fill(&visited[0][0],&visited[MAX-1][MAX],false);
	 	standard = k;
	 	int cnt =0; //영역 개수

	 	for(int i=0;i<N;i++) {
	  		for(int j=0;j<N;j++) {
				if(!visited[i][j] && k < map[i][j]) {
	 				dfs(i,j);
					cnt++;
				}
	  		}
    	}
		result = max(cnt,result);
	}
    
	cout<<result<<endl;
	return 0;
}