백준 2468번 C++

백준 2468번 안전 영역

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

2468번: 안전 영역

정답 코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
int N;
const int MAX = 101;
int input[MAX][MAX];
int map[MAX][MAX];
bool visited[MAX][MAX];
int dy[] = { 0,0,-1,1 };
int dx[] = { -1,1,0,0 };
queue<pair<int, int>> q;
vector<int> v; 
int cnt; 
 
void BFS(int y, int x) {
    visited[y][x] = true;
    q.push(make_pair(y, x));
 
    while (!q.empty()) {
        y = q.front().first;
        x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
 
            if (ny < 0 || nx < 0 || ny >= N || nx >= N)
                continue;
            if (map[ny][nx] && !visited[ny][nx]) {
                visited[ny][nx] = true;
                q.push(make_pair(ny, nx));
            }
        }
    }
}
 
void reset() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            map[i][j] = 0;
            visited[i][j] = 0;
        }
    }
    cnt = 0;
}
 
int main() {
    int maxHeight = -1;
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> input[i][j];
            if (input[i][j] > maxHeight) {
                maxHeight = input[i][j];
            }
        }
    }
 
    for (int h = 1; h <= maxHeight; h++) {

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (input[i][j] < h) {
                    map[i][j] = 0;
                }
                else {
                    map[i][j] = 1;
                }
            }
        }
 
       
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] && !visited[i][j]) {
                    BFS(i, j);
                    cnt++;
                }
            }
        }
        v.push_back(cnt);
        
        /*초기화*/
        reset();
    }
 
    sort(v.begin(), v.end()); 
    cout << v[v.size() - 1];  
}

문제 풀이

bfs를 이용해서 풀 수 있습니다. 문제 서론이 생각보다 길긴 하지만 의외로 단순합니다. 주어진 높이보다 높이가 낮은 곳들은 0으로 나머지 곳들은 1로 처리한 후
bfs를 돌리면 됩니다. 이때 시작하는 좌표들은 한 곳이 아니기 때문에 반복문을 돌리면서 찾을 때마다 bfs를 돌려주면 됩니다. 그리고 그때마다 count개수를 1개씩 더해주시면 됩니다.