[백준/Baekjoon] 2468 안전 영역 C++ :: BFS

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

2468번: 안전 영역

---

1. Logic

물에 잠기지 않는 지점이 최대가 될 때를 구하는 문제이다.

처음에 이 문제를 봤을 때 그냥 주변높이 보다 높으면 안전지역인줄 알았는데 문제를 다시 읽어보니 0~최대 높이까지 확인하면서 그중에 가장 많은 안전지역의 갯수를 구하는 문제이다.

 

풀이 방법은 입력을 받으면서 최대 높이를 구하고 0~최대 높이 까지 BFS를 돌면서 최대 안전 지역의 갯수를 구하면 된다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n;
int maxRain = 0;
int minRain = 0x3f3f3f3f;
int rainCnt = 0;

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

int graph[101][101];
bool vis[101][101];

void BFS(int yy, int xx, int limit) {
    queue<pair<int, int>> q;

    q.push({yy, xx});
    vis[yy][xx] = true;
    
    while(!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
               
            if (ny >= n || nx >= n || ny < 0 || nx < 0) continue;
            if (graph[ny][nx] <= limit) continue;
            if (vis[ny][nx]) continue;
            
            vis[ny][nx] = true;
            q.push({ny, nx});
        }
    }
}

int main() {
    ios_base::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 >> graph[i][j];
            if(maxRain < graph[i][j]) {
                maxRain = graph[i][j];
            }
            if(minRain > graph[i][j]) {
                minRain = graph[i][j];
            }
        }
    }
    
    for(int k = 0; k <= maxRain; k++) {
        memset(vis, false, sizeof(vis));
        int cnt = 0;
        
        for(int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(vis[i][j]) continue;
                if(graph[i][j] <= k) continue;
                BFS(i, j, k);
                cnt++;
            }
        }
        rainCnt = max(rainCnt, cnt);
    }
    
    cout << rainCnt;
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90