[백준] 2468번: 안전 영역 (C++)

 

www.acmicpc.net/problem/2468

2468번: 안전 영역

BFS로 간단하게 풀 수 있는 문제이다.

비가 내리지 않는 경우를 생각하지 않아서 계속 틀렸었다.

 

• 지역의 높이를 받을 때 가장 높은 지역의 높이를 high에 저장한다.
• 비가 내리지 않는 경우 k = 0 부터 k = high - 1 까지 오는 경우까지 BFS를 돌려서 최대 안전영역 수를 갱신시킨다.

 

 

소스코드

#include <bits/stdc++.h>
using namespace std;

int n, mx, high, result;
int m[100][100];
int vis[100][100];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0 ,0};

void bfs(int x, int y, int k) {
    queue<pair<int, int> > q;

    vis[x][y] = 1;
    q.push(make_pair(x, y));

    while(!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();

        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 (vis[nx][ny] || m[nx][ny] <= k) continue;

            vis[nx][ny] = 1;
            q.push(make_pair(nx, ny));
        }
    }
}

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

    cin >> n;
    for (int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> m[i][j];
            high = max(high, m[i][j]);
        }
    }

    
    for (int k = 0; k < high; k++) {
        for (int i = 0; i < n; i++) {
             for(int j = 0; j < n; j++) {
                 if (m[i][j] > k && !vis[i][j]) {
                    bfs(i, j, k);
                    result++;
                 }
            }
        }
        mx = max(mx, result);
        result = 0;
        memset(vis, 0, sizeof(vis));
    }
    cout << mx; 

    return 0;
}