[알고리즘] 2468번: 안전 영역

0. 문제

2468번: 안전 영역

 

---

1. 문제 이해

 

1. 연결된 컴포넌트의 수가 최대가 되는 높이 값을 구하는 문제
2. 최댓값을 구하기 위한 방법 → 모든 경우의 수를 실행하고 비교한다?

 

---

2. 제출

 

가. 실패

//백준 2468번: 안전 영역
#include <iostream>
#include <cstring>

using namespace std;

const int max_n = 100;
int n, max_h=0, ret=0; 
int a[max_n][max_n], visited[max_n][max_n];
int dy[] = {-1,0,1,0};
int dx[] = {0,1,0,-1};

void dfs(int y,int x, int h){
    visited[y][x] = 1;
    for(int i=0; i<4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        bool underflow = ny < 0 || nx < 0;
        bool overflow =  n <= ny || n <= nx; 
        if(underflow || overflow) continue;
        if(a[ny][nx] > h && !visited[ny][nx]){
            dfs(ny, nx, h);
        }
    }
    return;
}

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

    cin >> n;
    for(int y=0; y<n; y++){
        for(int x=0; x<n; x++){
            int tmp;
            cin >> tmp;
            if(max_h < tmp) max_h = tmp;    
            a[y][x] = tmp;
        }
    }
    for(int h=1; h<= max_h; h++){
        int cnt = 0;
        memset(visited, 0, sizeof(visited));
        for(int y=0; y<n; y++){
            for(int x=0; x<n; x++){
                if(a[y][x] > h && !visited[y][x]){
                    cnt++;
                    dfs(y, x, h);
                }
            }
        }
        if(ret < cnt) ret = cnt;
    }    
    cout << ret << "\n";

    return 0;
}

 

int tmp;
cin >> tmp;
if(max_h < tmp) max_h = tmp;    

100까지 실행하기보다 입력한 높이의 최댓값까지만 실행시키기 위해서.

 

if(a[y][x] > h && !visited[y][x]){

물에 잠기지 않는지 확인한다.

 

실패!!!!??

 

---

나. 수정

 

문제에 다음과 같은 설명이 있었다.

 

아무 지역도 물에 잠기지 않을 수도 있다.

 

이 말은 곧 비가 내리지 않을 수 있다는 뜻인 것 같다.

 

“비가 내리지 않을 수 있다”와 “아무 지역도 물에 잠기지 않을 수도 있다.”는 같은 의미는 아닌 것 같은데;;

 

//before
for(int h=1; h<= max_h; h++){
//after
for(int h=0; h<= max_h; h++){

 

//백준 2468번: 안전 영역
#include <iostream>

using namespace std;

const int max_n = 100;
int n, max_h=0, ret=0; 
int a[max_n][max_n], visited[max_n][max_n];
int dy[] = {-1,0,1,0};
int dx[] = {0,1,0,-1};

void dfs(int y,int x, int h){
	visited[y][x] = 1;
	for(int i=0; i<4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		bool underflow = ny < 0 || nx < 0;
		bool overflow = n <= ny || n <= nx; 
		if(underflow || overflow) continue;
		if(a[ny][nx] > h && !visited[ny][nx]){
			dfs(ny, nx, h);
		}
	}
	return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	fill(&a[0][0], &a[0][0] + 100 * 100, 0);

	cin >> n;
	for(int y=0; y<n; y++){
		for(int x=0; x<n; x++){
			int tmp;
			cin >> tmp;
			if(max_h < tmp) max_h = tmp;	
			a[y][x] = tmp;
		}
	}
	for(int h=0; h<= max_h; h++){
		int cnt = 0;
		fill(&visited[0][0], &visited[0][0] + 100 * 100, 0);
		for(int y=0; y<n; y++){
			for(int x=0; x<n; x++){
				if(a[y][x] > h && !visited[y][x]){
					cnt++;
					dfs(y, x, h);
				}
			}
		}
		if(ret < cnt) ret = cnt;
		//ret = max(ret, cnt);
	}	
	cout << ret << "\n";

	return 0;
}

 

---