[C++] 백준 BOJ 2468 안전 영역

문제링크 : https://boj.kr/2468

흰색으로 연결된 부분들의 갯수를 세는 문제다.

갯수를 세는 것은 DFS로 풀면 되는데.. 문제는 1~100까지의 비 내리는 높이들을 하나 하나 다 계산해봐서 영역이 가장 많은 것을 구하는 것이다.

어떻게 해야 효율적으로 구할 수 있을까 생각해봤는데.. 일단 풀었다.

1~100까지의 횟수는 그리 많은 횟수가 아니라 시간 복잡도 상으로도 O(1)에 해당하기 때문에..

그래서 1~100 까지의 모든 높이마다 각각 dfs를 그냥 돌렸는데 시간초과도 나지 않고 풀렸다.

이미 풀렸기 때문에 여기서 시간을 더 줄이는 효율적인 방법은 생각해보지 않았다.

혹시나 해서 입력 받을때 최소 높이, 최대 높이를 추가로 체크해서 풀었는데 어짜피 시간은 똑같이 나왔다. 별로 의미가 없는듯

차이를 보이지 않음..

// BOJ 2468 안전 영역
#include <bits/stdc++.h>
 
using namespace std;
vector<vector<int> > region;
vector<vector<bool> > visited;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
 
void dfs(int x, int y, int h) {
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (region[xx][yy] > h && !visited[xx][yy]) {
            visited[xx][yy] = true;
            dfs(xx, yy, h);
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("../input.txt", "r", stdin);
 
    int num;
    cin >> num;
    region = vector<vector<int> >(num + 2, vector<int>(num + 2));
    visited = vector<vector<bool> >(num + 2, vector<bool>(num + 2, false));
    for (int i = 1; i <= num; i++)
        for (int j = 1; j <= num; j++)
            cin >> region[i][j];
 
    int result = 1;
    for (int n = 1; n <= 100; n++) {
        // visited 초기화
        for (int i = 1; i <= num; i++)
            for (int j = 1; j <= num; j++)
                visited[i][j] = false;
 
        int cnt = 0;
        for (int i = 1; i <= num; i++) {
            for (int j = 1; j <= num; j++) {
                if (region[i][j] > n && !visited[i][j]) {
                    visited[i][j] = true;
                    dfs(i, j, n);
                    cnt++;
                }
            }
        }
        result = max(result, cnt);
    }
 
    cout << result;
 
    return 0;
}

최소~최대를 따로 구해서 풀어본 코드

// BOJ 2468 안전 영역
#include <bits/stdc++.h>
 
using namespace std;
vector<vector<int> > region;
vector<vector<bool> > visited;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
 
void dfs(int x, int y, int h){
    for(int i = 0; i < 4; i++){
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(region[xx][yy] > h && !visited[xx][yy]){
            visited[xx][yy] = true;
            dfs(xx, yy, h);
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("../input.txt", "r", stdin);
 
    int num;
    cin >> num;
    region = vector<vector<int> >(num + 2, vector<int>(num + 2));
    visited = vector<vector<bool> >(num + 2, vector<bool>(num + 2));
    int minH = 100;
    int maxH = 0;
    for(int i = 1; i <= num; i++) {
        for (int j = 1; j <= num; j++) {
            cin >> region[i][j];
            minH = min(minH, region[i][j]);
            maxH = max(maxH, region[i][j]);
        }
    }
 
    int result = 1; // 모든 영역이 하나도 안잠겼을 경우부터 시작
    for(int n = minH; n <= maxH; n++){
        // visited 초기화
        for(int i = 1; i <= num; i++)
            for (int j = 1; j <= num; j++)
                visited[i][j] = false;
 
        int cnt = 0;
        for(int i = 1; i <= num; i++) {
            for (int j = 1; j <= num; j++) {
                if (region[i][j] > n && !visited[i][j]){
                    visited[i][j] = true;
                    dfs(i, j, n);
                    cnt++;
                }
            }
        }
        result = max(result, cnt);
    }
 
    cout << result;
 
    return 0;
}