백준 //안전 영역

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

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm> // max 함수
using namespace std;

int N; // 맵 크기
vector<vector<int>> map; // 지역의 높이 정보
vector<vector<bool>> visited; // 방문 여부 확인용


// 4방향 (상하좌우)
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

// DFS 함수 정의
void DFS(int x, int y, int height)
{
    visited[x][y] = true;

    for (int dir = 0; dir < 4; ++dir)
    {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        // 범위 체크
        if (nx >= 0 && nx < N && ny >= 0 && ny < N)
        {
            // 방문 안했고, 잠기지 않는 곳일 때만 DFS
            if (!visited[nx][ny] && map[nx][ny] > height)
            {
                DFS(nx, ny, height);
            }
        }
    }
}

int getSafeZoneCount_DFS(int height)
{
    int count = 0;
    visited = vector<vector<bool>>(N, vector<bool>(N, false));

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            // 안전영역 시작점 발견
            if (!visited[i][j] && map[i][j] > height)
            {
                DFS(i, j, height);
                count++; // 하나의 안전 영역 완료
            }
        }
    }
    return count;
}

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

    while (!q.empty())
    {
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();

        for (int dir = 0; dir < 4; ++dir)
        {
            int nx = cx + dx[dir];
            int ny = cy + dy[dir];

            if (nx >= 0 && nx < N && ny >= 0 && ny < N)
            {
                if (!visited[nx][ny] && map[nx][ny] > height)
                {
                    visited[nx][ny] = true;
                    q.push({ nx, ny });
                }
            }
        }
    }
}

int getSafeZoneCount_BFS(int height)
{
    int count = 0;
    visited = vector<vector<bool>>(N, vector<bool>(N, false));

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


int main()
{
    cin >> N;
    map = vector<vector<int>>(N, vector<int>(N));
    int max_height = 0;

    // 입력 받기
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            cin >> map[i][j];
            max_height = max(max_height, map[i][j]);
        }
    }

    int result_dfs = 0;
    int result_bfs = 0;

    // 0부터 최대 높이까지 모든 비 높이에 대해 검사
    for (int h = 0; h <= max_height; ++h)
    {
        result_dfs = max(result_dfs, getSafeZoneCount_DFS(h));
        result_bfs = max(result_bfs, getSafeZoneCount_BFS(h));
    }

    cout  << "최대 안전 영역 개수 (DFS): "<<result_dfs << endl;
    cout << "최대 안전 영역 개수 (BFS): " << result_bfs << endl;

    return 0;
}