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

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

2468번: 안전 영역

<풀이>

1. 가능한 비의 높이마다 맵 탐색(BFS) 후, 안전영역 개수 구한다.

2. 가장 많은 안전영역 개수를 출력한다.

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
 
struct field {
    //영역 좌표
    int x, y;
};
 
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
 
int N;
int map[100][100];
bool visited[100][100];
queue<field> q;
int tmpRes;
int res = 0;
 
void bfs(int rain) {
    while (!q.empty()) {
        field cur = q.front();
        q.pop();
 
        //4방향 모두 탐색
        for (int i = 0; i < 4; i++) {
            field nxt = cur;
 
            nxt.x += di[i];
            nxt.y += dj[i];
 
            //범위를 벗어나는 경우 continue
            if (nxt.x < 0 || nxt.y < 0 || nxt.x >= N || nxt.y >= N) {
                continue;
            }
 
            //안전한 곳만 큐에 담기
            if (map[nxt.x][nxt.y] > rain && !visited[nxt.x][nxt.y]) {
                visited[nxt.x][nxt.y] = true;
                q.push(nxt);
            }
        }
    }
}
 
int main() {
 
    //입력
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
 
    //가능한 비의 높이마다 탐색
    for (int rain = 0; rain < 100; rain++) {
 
        //비 높이 때 사용되는 변수들 초기화
        memset(visited, false, sizeof(visited));
        tmpRes = 0;
 
        //맵 완전탐색
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                //안전한 곳 큐에 담고 bfs, 안전영역 찾기
                if (map[i][j] > rain && !visited[i][j]) {
                    field start;
                    start.x = i;
                    start.y = j;
 
                    q.push(start);
                    visited[start.x][start.y] = true;
                    bfs(rain);
 
                    //한 곳에서 안전한 영역을 찾으면, 안전영역++
                    tmpRes++;
                }
            }
        }
 
        //최대 안전영역 개수 저장
        res = max(tmpRes, res);
    }
 
    //출력
    cout << res << "\n";
}

 

BFS에 대해 알아볼 수 있는 문제였습니다.