https://www.acmicpc.net/problem/2468
입력
첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.
출력
첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.
풀이
접근방법 -> 먼저 n이하의 수를 모두 0으로 침수지역으로 지정
그 후 상하좌우로 안전지대의 수를 bfs로 탐색
근데 이게 아니었다 문제를 잘못이해 함
올바른 접근->이 문제는 만약 NXN 행렬의 하나의 블럭이 7이다 그럼
그 7의 값을 가지고 있는 블럭 값만큼 1~7까지 수를 올려가며 안전지대를 찾고
그 1~7까지의 각 루프마다(BFS실행) 한 값 중 제일 큰 안전지대의 수를 찾는 문제이다.
반례로는 3 11111111 일 시 1이 나와야한다.
문제 이해를 잘해야 하는 문제.
보통의 DFS,BFS+브루트포스 문제이지만 괜히 문제에 NXN 5 예시에서 4일때, 6일때를 나타낸게 아니다.
코드```
#include
#include
#include
#include
using namespace std;
typedef pair<int, int> Node;
int arr[101][101];
bool visitied[101][101];
int N;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int max_v;
vectorresult;
void check(int i, int j,int loop)
{
queueq;
q.push(Node(i, j));
visitied[i][j] = true;
while (!q.empty())
{
Node now = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int nx = dx[i] + now.first;
int ny = dy[i] + now.second;
if (nx >= 0 && ny >= 0 && nx < N && ny < N)
{
if (visitied[nx][ny] == false && arr[nx][ny]>loop)
{
visitied[nx][ny] = true;
q.push(Node(nx, ny));
}
}
}
}
}
void initail()
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
visitied[i][j] = false;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> arr[i][j];
if (i == 0 && j == 0) {
max_v = arr[i][j];
}
if (arr[i][j] > max_v)
{
max_v = arr[i][j];
}
}
}
int loop_value = 0;
while (loop_value <= max_v)
{
initail();
int cnt = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (visitied[i][j]==false&&arr[i][j]> loop_value)
{
cnt++;
check(i, j, loop_value);
}
}
}
loop_value++;
result.push_back(cnt);
}
cout << *max_element(result.begin(), result.end());
}
