#2468번 안전 영역 (C++)

링크 : www.acmicpc.net/problem/2468

2468번: 안전 영역

문제가 제법 길어서 요약은 패스했다.

해당 문제를 이해하는데 다소 시간이 걸렸다. 핵심 포인트를 요약하자면 다음과 같다. 

 

(1)

강수량의 높이보다 높은 5개의 구역들만 살아남게 된다. 

침수되지 않은 지역들은 위 / 아래 / 좌 / 우로 연결되어있으면 같은 하나의 지역으로 간주된다.

(2) 강수량의 높이는 정해지지 않았다.

(3) 비가 아예 안올수도 있다. 즉, 강수량이 0이라는 의미이다.

모든 지역의 높이는 최소 1부터 시작인데, 아무도 물에 안잠기려면 비는 0의 높이로 와야한다.

 

문제 풀이는 다음과 같다.

 

(1) 강수량은 0부터 입력된 값의 최대값까지로 간주한다. 

(2) 배열의 0,0부터 시작하여, 해당 지역이 강수량보다 높고 이전에 방문한 적이 없다면 (false) DFS를 진행한다.

(3) 해당 위치는 방문한 것으로 표기하며 (true), 해당 위치의 위 / 아래 / 좌 / 우 중 다음 조건을 만족할 경우, 다시 DFS를 진행한다. 

-> 조건 : x,y 좌표값이 0보다 작지 않고 n 이상의 값을 갖지 않으며, 해당 위치의 값이 강수량보다 높고 방문한 적이 없어야 한다. 

(4) 이렇게 해서 얻게 된 침수되지 않은 지역(temp)이 여탯껏 구한 값중 가장 큰 값(cnt)보다 크면 cnt의 값을 temp로 변경해준다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int n = 0, maxi = 0, temp = 0, cnt = 0, nx=0, ny=0;
int v[100][100];
bool check[100][100] = {false,};
int mx[4] = {1,0,-1,0}; //위 아래 좌 우 도표
int my[4] = {0,1,0,-1};

bool track(int y, int x, int h){
    if(y>=n||y<0||x>=n||x<0||v[y][x]<=h||check[y][x]) return false;
    return true;
}

void dfs(int y, int x, int h){
    check[y][x] = true;
    for(int i=0; i<4; i++){
        ny = y+my[i];
        nx = x+mx[i];
        if(track(ny,nx,h)==true){
            dfs(ny,nx,h);
        }
    }
}

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

    cin >> n;   
    int h = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> h;
            v[i][j] = h;
            if(h>maxi) maxi = h; //최대치로 오는 비의 양을 기록
        }
    }
    h = 0;    
    while(h<=maxi){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(v[i][j]>h&&check[i][j]==false){
                    dfs(i,j,h);
                    temp++;
                }
            }
        }
        if(temp>cnt) cnt = temp;
        memset(check,false,sizeof(check));
        temp = 0;
        h++;
    }
    cout << cnt << "\n";
    return 0;
}