[BOJ 2468] 안전 영역

백준 :: BOJ :: 2468 :: 안전 영역

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

#include <iostream>

#include <memory.h>

#include <algorithm>

#include <queue>

using namespace std;

int N, maxH, cnt, ans;

int map[100][100];

bool visited[100][100];

int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };

queue <pair<int,int>> q;

inline bool check(int i, int j, int h) { return ((i>=0 && j>=0 && i<N && j<N 

&& !visited[i][j] && map[i][j]>h) ? true : false); }

void bfs(int i, int j, int h) {

visited[i][j] = true;

q.push(make_pair(i,j));

int ii, jj;

while (!q.empty()) {

ii = q.front().first; jj = q.front().second; q.pop();

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

int ni = ii + dir[d][0]; int nj = jj + dir[d][1];

if (check(ni, nj, h)) {

visited[ni][nj] = true;

q.push(make_pair(ni, nj));

}

}

}

}

int main() {

cin >> N; maxH = 0; ans = 1;

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

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

cin >> map[i][j];

maxH = max(maxH, map[i][j]);

}

}

for (int h = 1; h < maxH; h++) {

memset(visited, 0, sizeof(visited)); cnt = 0;

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

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

if (map[i][j]>h && !visited[i][j]) {

bfs(i, j, h); cnt++;

}

}

}

ans = max(ans, cnt);

}

cout << ans << endl;

return 0;

}