백준 2468 (C++) 안전 영역

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

2468번: 안전 영역

 

 

 

q.pop()을 빼먹어서 queue 길이가 자꾸만 증가하는 이유를 찾으려 디버깅을 계속했다...  ㅠㅠ

 

76%에서 틀렸었는데, 아무 칸도 물에 잠기지 않을 수 있다는 조건을 빼먹었기 때문이다.

 

 

 

 

유사 문제

 

 

떨어진 영역(뭉탱이)의 개수를 구하는 방법을 모르겠다면 아래 문제와 해답을 참고하면 도움될 것이다.

 

2021.09.26 - [PS/백준] - 백준 4963번 (C++) 섬의 개수

백준 4963번 (C++) 섬의 개수

 

 

 

 

 

 

 

 

풀이

 

주어진 입력을 받은 후,

물에 잠긴 영역을 rain이라는 이차원 배열에 체크했다.

(잠겼다면 1, 잠기지 않았다면 0)

 

 

bfs는 너비 우선 탐색으로,

이차원 배열의 그래프를 탐색할 때는 보통 dx, dy 등 배열을 사용하여 인접 영역을 방문 체크하며 탐색한다.

 

 

각 칸마다 bfs로 방문하고, 인접 칸을 visited == true로 체크한다.

 

 

그 칸에 인접하지 않은 영역과, 물에 잠기지 않은 영역은 방문되지 않을 것이다.

 

 

그렇다면 하나의 칸을 bfs로 방문했을 때,

bfs함수가 종료됨과 동시에 그 칸에 인접한 칸들은 전부 방문체크가 되어있다.

 

 

따라서 rain이라는 이차원 배열에 iteration을 진행하며

칸이 물에 잠겨있지 않고, 이미 방문한 곳도 아니라면 cnt++한다.

 

 

최대 높이가 100이므로 0에서 100까지 높이를 증감하며 max함수로 최대 cnt값을 찾고 그것을 출력한다.

 

 

 

 

 

 

---

 

코드

 

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX = 100;
int N,M,K;
int arr[MAX][MAX];
int rain[MAX][MAX]; // 물에 잠긴 후 시뮬레이션을 위한 배열
bool visited[MAX][MAX] = {false, };
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

void bfs(int a, int b) {
    queue<pair<int, int>> q;
    q.push({a, b});
    visited[a][b] = true;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int it = 0; it < 4; it++) {
            int nx = x + dx[it];
            int ny = y + dy[it];
            if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
                continue;
            }
            if (visited[nx][ny] || rain[nx][ny]) {
                continue;
            }
            visited[nx][ny] = true;
            q.push({nx, ny});
        }
    }
    return;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int cnt = 0, ans = 0;
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
            rain[i][j] = 0;
        }
    }
    for (int k = 0; k <= 100; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] <= k) {
                    rain[i][j] = 1; // 물에 잠기면 1
                }
            }
        } // 이제 rain에 잠긴 곳만 표시되어 있음
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!rain[i][j] && !visited[i][j]) { // 잠긴 곳이 아니라면 탐색
                    cnt++;
                    bfs(i, j);
                }
            }
        }
        ans = max(ans, cnt);
        // 초기화
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                rain[i][j] = 0;
                visited[i][j] = false;
                cnt = 0;
            }
        }
    }
    cout << ans;
    return 0;
}