BOJ 2468 안전영역

📎Problem Link

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

2468번: 안전 영역

 

📋 문제 정리

• 침수되지 않은 안전한 구간 세기
• 지역의 높이 정보는 2차원 배열 & 행과 열은 N으로 동일
• 각 지역의 높이 정보는 
• 첫째 줄에는 N 입력
• 둘째줄부터 N개의 줄에는 자연수로 각 지역의 높이 입력 (이 때, 높이는 1이상 100 이하의 정수)

 

📌 예제 1

예제 1을 그림으로 나타내면 위와 같다. 위의 표에서 제일 최대 높이로 가질 수 있는 9까지의 경우를 봤을 때 최대 안전지역 개수는 N=4, 5일 때 5개이다.

 

 

📌 예제 2

예제 2를 그림으로 나타내면 위와 같다. 위의 표에서 제일 최대 높이로 가질 수 있는 9까지의 경우를 봤을 때, 최대 안전 지역 개수는 N=7일 때 6이다.

---

💻 Code

#include<iostream>
#include<algorithm>
#include<queue>
#define MAX 100
using namespace std;
int mx[4] = { 0, 0, 1, -1 };
int my[4] = { 1, -1, 0, 0 };

class Country {
public:
	int N;
	int map[MAX][MAX];
	int visited[MAX][MAX] = { 0 };
	queue <pair<int, int>> q;

	void DFS(int l, int y, int x) {
		q.push(make_pair(y, x));
		
		while (!q.empty()) {
			int cy = q.front().first;
			int cx = q.front().second;
			q.pop();

			for (int i = 0; i < 4; i++) {
				int ny = cy + my[i];
				int nx = cx + mx[i];

				if (ny < 0 || ny >= N || nx < 0 || nx >= N)
					continue;

				if ((map[ny][nx] > l) && !visited[ny][nx])
				{
					visited[ny][nx] = 1;
					q.push(make_pair(ny, nx));
				}
			}

		}
	}
};

int main() {
	int limit_max = 0;
	int result = 1;
	int temp = 0;
	Country rainy;

	cin >> rainy.N;

	for (int i = 0; i < rainy.N; i++) {
		for (int j = 0; j < rainy.N; j++) {
			cin >> rainy.map[i][j];
			limit_max=std::max(limit_max, rainy.map[i][j]);
		}
	}

	for (int i = 1; i <= limit_max; i++) {
		temp = 0;
		memset(rainy.visited, 0, sizeof(rainy.visited));
		for (int j = 0; j < rainy.N; j++) {
			for (int k = 0; k < rainy.N; k++) {
				if (i < rainy.map[j][k] && !rainy.visited[j][k])
				{
					rainy.visited[j][k] = 1;
					rainy.DFS(i, j, k);
					temp++;
				}
			}
		}
		result = max(temp, result);
	}
	cout << result << endl;
}

 

 

 

---