백준 2468 안전 영역

#include <cstdio>

#include <iostream>

#include <queue>

#include <memory.h>

using namespace std;

int N; // 테케, 가로, 세로, 배추 심어진 갯수

int arr[110][110];

bool visit[110][110] = { false, };

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

queue<int> queueX, queueY;

void bfs(int x, int y)

{

queueX.push(x); queueY.push(y);

visit[x][y] = true;

//queue가 비어있지 않을 경우 반복

while (!queueX.empty() && !queueY.empty()){

int tempX = queueX.front(), tempY = queueY.front();

queueX.pop(); queueY.pop();

for (int dir = 0; dir < 4; dir++){

int nextX = tempX + dx[dir], nextY = tempY + dy[dir];

//맵 밖으로 나가지 않는 경우만

if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < N){

if (visit[nextX][nextY] == false){

visit[nextX][nextY] = true;

queueX.push(nextX);

queueY.push(nextY);

}

}

}

}

}

int main()

{

int highest_H = 0, ans = 0; //, lowest_H = 2e9

scanf(" %d", &N);

for (int i = 0; i < N; i++){

for (int j = 0; j < N; j++){

scanf(" %d", &arr[i][j]);

highest_H = highest_H > arr[i][j] ? highest_H : arr[i][j]; //최고 높이 저장

//lowest_H = lowest_H < arr[i][j] ? lowest_H : arr[i][j]; // 최저 높이 저장 ※잠기는 높이는 0부터 시작하므로 의미는 없다.

}

}

//깊이별로 반복하면서 침수지역 만들어서 bfs에 넘겨서 안전영역의 최대 개수를 출력한다.

for (int h = 0; h < highest_H; h++){

int cnt = 0;

//visit 배열 false로 초기화 필요

memset(visit, false, sizeof(visit));

//침수 처리

for (int i = 0; i < N; i++){

for (int j = 0; j < N; j++){

//해당 물높이일 때 침수되는 위치라면

if (arr[i][j] <= h){

visit[i][j] = true;

}

}

}

//안전지역 탐색

for (int i = 0; i < N; i++){

for (int j = 0; j < N; j++){

//침수되지 않은 위치라면 bfs를 실행한다.

if (visit[i][j] == false){

++cnt; // 안전지역 갯수 새기 위함

bfs(i, j);

}

}

}

ans = ans > cnt ? ans : cnt;

}

printf("%d \n", ans);

return 0;

}