[BOJ/C++] 2468 안전 영역

시간 복잡도

• N이 최대 100, 높이가 최대 100이기 때문에 $N*N$ 을 높이만큼 반복하면 최대 1,000,000 입니다.
• BFS를 인접 행렬로 구현하면 $O(V*E)$이고 높이만큼 반복하기 때문에 시간 복잡도는 $O(N^2 * h)$ 입니다.

문제 접근법

• 장마철에 비가오는 모든 높이에 대해 BFS를 진행하며 해당 높이보다 높은 곳을 탐색합니다.
• 탐색에 성공한 BFS는 하나의 안전 영역이 되므로 안전 영역의 개수를 카운트합니다.
• 모든 높이에 대해 안전 영역의 개수의 최댓값으로 업데이트합니다.

코드

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>


using namespace std;

using int32 = long;
using int64 = long long;

static vector<vector<int>> G;
static vector<vector<int>> visited;

static int N = 0;

static int dy[] = {-1, 1, 0, 0};
static int dx[] = { 0, 0, -1, 1};

void BFS(int y, int x, int height);

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N;

    G = vector<vector<int>>(N, vector<int>(N, 0));

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            cin >> G[i][j];
    }

    int answer = 1;

    for(int k=1; k<100; k++)
    {
        int count = 0;

        visited = vector<vector<int>>(N, vector<int>(N, false));

        for(int i=0; i<N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if(!visited[i][j] && G[i][j] > k)
                {
                    BFS(i, j, k);
                	count++;
                }
            }
                
        }

        answer = max(answer, count);
    }

    cout << answer;

    return 0;
}

void BFS(int y, int x, int height)
{
    visited[y][x] = true;
    queue<pair<int, int>> q;

    q.push({y, x});

    while(!q.empty())
    {
        int nowY = q.front().first;
        int nowX = q.front().second;

        q.pop();

        for(int i=0; i<4; i++)
        {
            int nextY = nowY + dy[i];
            int nextX = nowX + dx[i];
            
            if(nextY >=0 && nextY <N && nextX>=0 && nextX<N)
            {
                if(!visited[nextY][nextX] && G[nextY][nextX] > height)
                {
                    visited[nextY][nextX] = true;
                    q.push({nextY, nextX});
                }
            }
        }
    }
}