[백준] 안전영역 (2468/C++)

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

2468번: 안전 영역

 

코드 설명

강수량 높이를 0부터 하지 않아서 계속해서 반례를 찾아보느라 시간이 오래 걸렸다.

그 외 while안에 이중 for문을 담아서 계속해서 visited배열을 초기화시켜주면서 안전영역이 가장 많을 때를 저장했다.

 

N^3이지만 100^3이라 복잡도면에서 괜찮을 것이라 판단했다.

 

(반례)

3

1 1 1

1 1 1

1 1 1

을 했을때 답:1 이 나와야 한다.

 

코드

//안전한영역의 개수가 최대인경우 찾기
#include<iostream>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,1,-1 };
int map[101][101];

bool visited[101][101];
int N;
void run(int h,int y,int x) {
	queue<pair<int, int>> q;
	visited[y][x] = true;
	q.push({ y,x });

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || nx >= N || ny >= N) continue;
			if (!visited[ny][nx] && map[ny][nx] > h) {
				q.push({ ny,nx });
				visited[ny][nx] = true;


			}


		}



	}

}
int main() {
	cin >> N;
	int max = 0;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cin >> map[y][x];
			if (map[y][x] > max) max = map[y][x];
		}
	}
	//////////

	////
	int aanswer = 0;
	int start = 0;
	while (start <= max) {
		int answer = 0;
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				if (!visited[y][x] && map[y][x]>start) {
					run(start,y, x);
					answer++;
				}

			}
		}
		if (aanswer < answer) aanswer = answer;
		start++;
		memset(visited, false,sizeof(visited));
	}
	cout << aanswer;



	return 0;
}