[알고리즘] 백준 2468

백준 2468번 안전영역

해결 과정 요약

우선 완전탐색을 여러번 해야하는 문제이므로 DFS를 이용한다.
단 물에 잠기는 부분이 비가 온 양에따라 계속 달라지므로 어쩔 수 없이
높이 0부터 100까지 모두 확인해주어야 한다.
높이별로 또 정점별로 DFS를 호출해주고 ret값을 최신화 시켜준다.

풀이

#include <bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
typedef long long ll;

int n,ret = 0;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int a[104][104];
int v[104][104];

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

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

    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> a[i][j];
        }
    }
    for(int h=0; h<=100; h++){
        fill(v[0], v[0]+sizeof(v)/sizeof(v[0][0]), 0);
        int tmp = ret;
        ret = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(a[i][j] > h && v[i][j] == 0){
                    ret++;
                    dfs(i, j, h);
                }
            }
        }
        ret = max(tmp, ret);
    }
    cout << ret;
    
    return 0;
}

트러블슈팅

• 처음에 비가 온 높이를 1부터 100 까지 탐색해서 육지높이가 1인 경우 오류가 났다.
  • 0부터 탐색하여 해결