2468번 안전영역

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <list>

using namespace std;

#define MAX 101
int N, answer;
int height;
int visited[MAX][MAX];
int map[MAX][MAX];

// 동서남북
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };

int safetyArea;
queue<pair<int, int>> q;

void Input()
{
    cin >> N;
    for (int x = 0; x < N; x++)
    {
        for (int y = 0; y < N; y++)
        {
            cin >> map[x][y];
            if (height < map[x][y])
                height = map[x][y];
        }
    }
}

void reset()
{
    safetyArea = 0;
    for (int x = 0; x < N; x++)
    {
        for (int y = 0; y < N; y++)
        {
            visited[x][y] = 0;
        }
    }
}
void bfs(int height)
{
    while (!q.empty())
    {
        pair<int, int> cur = q.front();
        q.pop();
        visited[cur.first][cur.second] = 1;

        for (int dir = 0; dir < 4; dir++)
        {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
            // 배열 범위 벗어나는지 체크
            if (nx < 0 || nx >= N || ny < 0 || ny >= N)
                continue;

            // 방문할 지역의 높이가 잠긴 구역보다 낮다면 안전 구역이 아니므로 생략
            if (map[nx][ny] <= height || visited[nx][ny] == 1)
                continue;
            visited[nx][ny] = 1;

            q.push({ nx, ny });
        }
    }
}

void Solution()
{
    while (height >= 0)
    {
        for (int x = 0; x < N; x++)
        {
            for (int y = 0; y < N; y++)
            {
                // 잠긴 높이보다 지역 높이가 크다면 안전 구역이므로 탐색 시작
                if (map[x][y] > height && visited[x][y] == 0)
                {
                    q.push({ x, y });
                    bfs(height);
                    safetyArea++;
                }
            }
        }
        if (answer < safetyArea)
            answer = safetyArea;

        reset();
        height--;
    }
}

void Solve()
{
    Input();
    Solution();
    cout << answer << '\n';
}

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

1. 높이 값을 맨 마지막값과 비교 해본다.

2. if (map[x][y] > height && visited[x][y] == 0) { q.push({ x, y }); bfs(height); safetyArea++; }

3. 이부분을 참고해서 다시 풀어보자…

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <list>

using namespace std;

#define MAX 101
int Map[MAX][MAX];
int visited[MAX][MAX] = { false };
int N, Answer;
int Height = 1;
int dr[4] = {-1,1,0,0};
int dc[4] = {0,0,-1,1};
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> Map[i][j];
            Height = max(Height, Map[i][j]);
                
        }
    }
}

void BFS(pair<int,int> here)
{
    queue<pair<int,int>> q;
    visited[here.first][here.second] = true;
    q.push(here);
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int NextX = x + dc[i];
            int NextY = y + dr[i];
            if (NextX >= 0 && NextX <= N && NextY >= 0 && NextY <= N && visited[NextX][NextY] == 0)
            {
                visited[NextX][NextY] = 1;
                if (Map[NextX][NextY] <= Height) continue;
                q.push({ NextX,NextY });
            }
        }
    }
}
vector<int> test;
void reset() {

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            visited[i][j] = 0;
        }
    }
    Height--;
}
void Solution()
{

    while (Height >= 0)
    {
        int count = 0;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if ( Map[i][j] > Height && visited[i][j] == 0)
                {
                    BFS({ i,j });
                    count++;
                }

            }
        }

        test.push_back(count);
        if (Answer < count)
            Answer = count;
        reset();
     
    }

}


void Solve()
{
    Input();
    Solution();
    cout << Answer << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Answer = 0;
    Solve();
}