백준 2468 안전 영역 c++

 

 

 

처음 작성한 코드는 다음과 같다.

주어진 예제는 잘 해결했으나, 틀렸다는 결과가 나왔다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// DFS 함수를 통해 1로 연결된 영역을 찾는다.
void dfs(vector<vector<int>>& matrix, int i, int j) {
    int m = matrix.size();
    int n = matrix[0].size();

    // 방문한 영역은 0으로 변경하여 중복 방문을 방지한다.
    matrix[i][j] = 0;

    // 현재 위치에서 상하좌우로 이동하면서 1인 영역을 탐색한다.
    vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    for (auto& dir : directions) {
        int ni = i + dir.first;
        int nj = j + dir.second;
        if (ni >= 0 && ni < m && nj >= 0 && nj < n && matrix[ni][nj] == 1) {
            dfs(matrix, ni, nj);
        }
    }
}

// 1로 표현된 영역의 개수를 반환하는 함수
int countIslands(vector<vector<int>>& matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    int count = 0;

    // 모든 위치를 순회하면서 1로 표시된 영역을 찾는다.
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j] == 1) {
                // 새로운 영역을 발견하면 카운트를 증가시키고, DFS를 통해 이어진 영역을 모두 탐색한다.
                ++count;
                dfs(matrix, i, j);
            }
        }
    }
    return count;
}

int main(){
    int n;
    cin >> n;
    
    vector<vector<int>> arr(n, vector<int>(n));
    int max_val = 0;
    int min_val = 101;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            cin >> arr[i][j];
            if(arr[i][j] > max_val)
                max_val = arr[i][j];
            if(arr[i][j] < min_val)
                min_val = arr[i][j];
        }
    }

    int count = 0;
    for(int i = min_val; i <= max_val; ++i){
        vector<vector<int>> matrix(n, vector<int>(n));
        for(int j = 0; j < n; ++j){
            for(int k = 0; k < n; ++k){
                if(i < arr[j][k])
                    matrix[j][k] = 1;
                else
                    matrix[j][k] = 0;
            }
        }

        int result = countIslands(matrix);
        if(count < result)
            count = result;
    }

    cout << count;
    return 0;
}

 

 

 

다시 작성한 코드는 다음과 같다.

큰 문제는 아니었고, 단지 강수량(높이=0)이 0인 경우도 고려해주어야 했다.

1. 주어진 n과 행렬을 입력받는다.

2. 0부터 가장 높은 높이(i)의 경우까지 고려해주며 영역의 개수를 센다.

2-1. (강수량보다 더 커서 땅이 잠기지 않으면 1, 땅이 잠기면 0으로 행렬을 선언)

2-2. (그 행렬을 dfs로 옮겨 1이 나타내는 영역의 개수를 셈)

3. 카운트한 영역 개수가 가장 큰 경우를 출력한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// DFS 함수를 통해 1로 연결된 영역을 찾는다.
void dfs(vector<vector<int>>& matrix, int i, int j) {
    int m = matrix.size();
    int n = matrix[0].size();

    // 방문한 영역은 0으로 변경하여 중복 방문을 방지한다.
    matrix[i][j] = 0;

    // 현재 위치에서 상하좌우로 이동하면서 1인 영역을 탐색한다.
    vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    for (auto& dir : directions) {
        int ni = i + dir.first;
        int nj = j + dir.second;
        if (ni >= 0 && ni < m && nj >= 0 && nj < n && matrix[ni][nj] == 1) {
            dfs(matrix, ni, nj);
        }
    }
}

// 1로 표현된 영역의 개수를 반환하는 함수
int countIslands(vector<vector<int>>& matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    int count = 0;

    // 모든 위치를 순회하면서 1로 표시된 영역을 찾는다.
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j] == 1) {
                // 새로운 영역을 발견하면 카운트를 증가시키고, DFS를 통해 이어진 영역을 모두 탐색한다.
                ++count;
                dfs(matrix, i, j);
            }
        }
    }
    return count;
}

int main(){
    int n;
    cin >> n;
    
    vector<vector<int>> arr(n, vector<int>(n));
    int max_val = 0;
    int min_val = 101;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            cin >> arr[i][j];
            if(arr[i][j] > max_val)
                max_val = arr[i][j];
            if(arr[i][j] < min_val)
                min_val = arr[i][j];
        }
    }

    int count = 0;
    for(int i = 0; i <= max_val; ++i){
        vector<vector<int>> matrix(n, vector<int>(n));
        for(int j = 0; j < n; ++j){
            for(int k = 0; k < n; ++k){
                if(i < arr[j][k])
                    matrix[j][k] = 1;
                else
                    matrix[j][k] = 0;
            }
        }

        int result = countIslands(matrix);
        if(count < result)
            count = result;
    }

    cout << count;
    return 0;
}