알고리즘 공부
백준 안전 영역
컴퓨터과학
2023. 7. 9. 22:43
https://www.acmicpc.net/problem/2468
2468번: 안전 영역
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는
www.acmicpc.net
처음시작인 높이 1부분 주의할것
#include <iostream>
#include <vector>
#include <algorithm>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<bitset>
using namespace std;
void Prints(vector<vector<char>>maps, int r, int c) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cout << maps[i][j];
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<bool>>maps, int r, int c) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cout << maps[i][j];
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<int>>maps, int r, int c) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cout << maps[i][j];
}
cout << endl;
}
cout << endl;
}
struct Data {
int r;
int c;
};
int main() {
int n;
int gCount = 0;
//n = 5;
cin >> n;
int max = 0;
vector<vector<int>>maps;
for (int i = 0; i < n; i++) {
vector<int>tmpMaps;
for (int j = 0; j < n; j++) {
int tmp;
cin >> tmp;
tmpMaps.push_back(tmp);
}
maps.push_back(tmpMaps);
}
for (int i = 0; i <= 100; i++) {
vector<bool>tmpVisited(n, false);
vector<vector<bool>>bVisited(n, tmpVisited);
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if (maps[j][k] <= i) {
bVisited[j][k] = true;
}
}
}
gCount = 0;
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if (bVisited[j][k]==false) {
queue<Data>q;
Data tmp;
tmp.c = k;
tmp.r = j;
bVisited[j][k] = true;
q.push(tmp);
gCount++;
if (max < gCount) {
max = gCount;
}
while (!q.empty()) {
Data start = q.front();
q.pop();
int dirR[] = {1,-1,0,0};
int dirC[] = {0,0,1,-1};
for (int u = 0; u < 4; u++) {
int tmpDirR = start.r+ dirR[u];
int tmpDirC = start.c + dirC[u];
if (tmpDirR == -1 || tmpDirC == -1 || tmpDirC >= n || tmpDirR >= n)
{
continue;
}
if (bVisited[tmpDirR][tmpDirC]==true) {
continue;
}
Data tmpD;
tmpD.c = tmpDirC;
tmpD.r = tmpDirR;
bVisited[tmpDirR][tmpDirC] = true;
q.push(tmpD);
}
}
}
}
}
if (gCount == 0) {
i = 101;
}
}
cout << max << endl;
return 0;
}