알고리즘 문제
[C/C++ 백준 2468번] 안전 영역 (Silver 1)
새파란 공대생
2020. 10. 17. 10:24
2468번: 안전 영역
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 �
www.acmicpc.net
범위가 굉장히 작아서, 모두 찾아줘도 무관하다. 모든 범위(H)에 대해 안전 영역을 찾아보자.
floodfill을 이용해 모든 점에 대해 탐색을 진행하여 영역을 세어주면 된다.
#include <cstdio>
#include <algorithm>
using namespace std;
int N, graph[101][101], cnt, maxi = -1;
bool visit[101][101];
void fill(int x, int y, int height){
if(x<0 || y<0 || x>=N || y>=N)
return ;
if(!visit[x][y] && graph[x][y]>=height){
visit[x][y] = true;
fill(x+1, y, height);
fill(x-1, y, height);
fill(x, y+1, height);
fill(x, y-1, height);
}
}
int main(void){
scanf("%d", &N);
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
scanf("%d", &graph[i][j]);
}
}
int height = 1;
while(height<=100){
cnt = 0;
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
visit[i][j] = false;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(!visit[i][j] && graph[i][j]>=height)
cnt++;
fill(i, j, height);
}
}
maxi = max(cnt, maxi);
height++;
}
printf("%d", maxi);
}