[C++]2468번 : 안전 영역

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

2468번: 안전 영역

 

해당 문제는 비의 높이에 따라 달라지는 connected component 중 갯수가 최대가 되는 경우를 구하는 문제이다.

강의에서는 arr를 따로 하나 더 구현하지는 않았지만, 본인은 safeArr이라는 배열을 하나 더 만들어서 문제를 해결했다.

배열을 하나 더 만들면 메모리 측면에서 손해가 있지만, 문제의 범위가 최대 100*100이기 때문에 큰 문제는 없을 듯 하다.

#include <bits/stdc++.h>
int arr[101][101];
int safeArr[101][101];
int visited[101][101];
int n;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {-1, 1, 0, 0};
using namespace std;
void dfs(int x, int y){
    visited[x][y] = 1;
    for(int i = 0; i < 4; i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx < 0 || nx >= n || ny < 0 || 
        ny >= n || visited[nx][ny] || !safeArr[nx][ny]) continue;
        dfs(nx, ny);
    }
}


int main(){
    cin >> n;
    int max = 1;
    for(int x = 0; x < n*n; x++){
        cin >> arr[x/n][x%n];
    }
    for(int height = 1; height <= 100; height++){
        int c = 0;
        fill(&safeArr[0][0], &safeArr[0][0]+101*101, 0);
        fill(&visited[0][0], &visited[0][0]+101*101, 0);
        for(int h = 0; h < n*n; h++){
            if(height < arr[h/n][h%n]) safeArr[h/n][h%n] = 1;
        }
        for(int x = 0; x < n; x++){
            for(int y = 0; y < n; y++){
                if(!visited[x][y] && safeArr[x][y]){
                    dfs(x, y);
                    c++;
                }
            }
        }
        if(max < c) max = c;
    }
    cout << max;
}

높이를 1부터 100까지 늘려 가며 잠기지 않는 곳을 1로 처리해 safeArr에 저장해 주고, 해당 배열을 가지고 DFS를 수행해 connected component의 갯수를 구한다. 이 동작을 반복한 뒤 최댓값을 출력한다.

높이 정보를 입력받을 때 높이의 최댓값을 저장해두었다가 height을 반복할 때 해당 높이까지만 반복하도록 하면 수행 시간을 더 줄일 수 있다.