[c++] 백준 2468 - 안전 영역

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

2468번: 안전 영역

• *max_element(vector<int> first, vector<int> last): 벡터가 가지고 있는 요소 중 가장 큰 값을 참조한다. 가장 작은 값을 받아오고 싶을 경우 '*min_element'를 사용하면 된다.

사용 예시

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    vector<int> v;

    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);

    int maxIdx = max_element(v.begin(), v.end()) - v.begin();
    int max = *max_element(v.begin(), v.end());

    int minIdx = min_element(v.begin(), v.end()) - v.begin();
    int min = *min_element(v.begin(), v.end());

    cout << "최대값의 인덱스: " << maxIdx << endl;
    cout << "최대값: " << max << endl;
    cout << "최소값의 인덱스: " << minIdx << endl;
    cout << "최소값: " << min << endl;
}

// 결과
//최대값의 인덱스: 4
//최대값: 50
//최소값의 인덱스: 0
//최소값: 10

 

코드

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAX 100
#define _X first
#define _Y second

int board[MAX][MAX];
bool visited[MAX][MAX];

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

int N;
int maxHeight = -1;     // 최대 높이 초기화

vector<int> vecArea;    // 각 높이에 대한 영역의 수 저장

void Dfs(int x, int y, int h)
{
    visited[x][y] = true;

    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
        if (visited[nx][ny] || board[nx][ny] <= h) continue;
        visited[nx][ny] = true;
        Dfs(nx, ny, h);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            // 배열 입력
            cin >> board[i][j];
            
            // 최대 높이 저장
            if (maxHeight < board[i][j])
                maxHeight = board[i][j];
        }
    }

    int area = 0;
    int maxArea = 0;

    // 높이가 1부터 최대 높이의 횟수만큼 물에 잠기지 않는 구역을 탐색
    for (int h = 1; h <= maxHeight; h++)
    {
        // 방문 배열 초기화
        memset(visited, false, sizeof(visited));

        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (board[i][j] > h && !visited[i][j])
                {
                    Dfs(i, j, h);
                    area++;
                }
            }
        }
        
        // 모든 높이에 대해 잠기지 않는 영역을 벡터에 저장
        vecArea.push_back(area);

        // 아무 지역도 물에 잠기지 않았을 경우 1로 세팅
        if (area == 0) vecArea.push_back(1);

        // 영역 초기화
        area = 0;
    }

    // 벡터 컨테이너의 최대값 구함
    int max = *max_element(vecArea.begin(), vecArea.end());
    cout << max;

    return 0;
}