[baekjoon 2468] 안전영역 - 그래프탐색(BFS, DFS)

www.acmicpc.net/problem/2468

2468번: 안전 영역

기본적으로 배열에 데이터를 받아서 그래프 탐색을 수행하는 문제였다.

다만 문제 마지막 조건에 아무 지역도 물에 잠기지 않을 수 있다는 조건으로 바로 맞추진 못했다..

 

#include <iostream>
#include <queue>
using namespace std;

int bound[101][101], N, height, resultMax, xmove[4] = { 1, -1, 0, 0 }, ymove[4] = { 0, 0, 1, -1 };
bool check[101][101];

void BFS2(int i, int j, int key) {
	queue<pair<int, int>> q;
	q.push(make_pair(i, j));
	check[i][j] = true;

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

		for (int i = 0; i < 4; i++) {
			int tempX = x + xmove[i];
			int tempY = y + ymove[i];
			if (bound[tempX][tempY] > key && !check[tempX][tempY] && tempX < N && tempY < N && tempX >= 0 && tempY >= 0) {
				q.push(make_pair(tempX, tempY));
				check[tempX][tempY] = true;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> bound [i][j];
			if (height < bound[i][j])
				height = bound[i][j]; // 높이정보범위용
		}
	}
	if (height >= 100)
		height = 100;

	for (int k = 0; k <= height; k++) {
		int count = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				check[i][j] = false;
			}
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (bound[i][j] > k && !check[i][j]) {
					count += 1;
					BFS2(i, j, k);
				}
			}
		}
		if (resultMax < count)
			resultMax = count;
	}
	if (resultMax == 0)
		cout << 1;
	else
		cout << resultMax;
}

입력을 받은 후, 높이가 1부터 100이지만 1~100을 모두 비교하기엔 비효율적이라고 생각이 들어서 입력되는 element값 중에서 가장 큰 값을 최대높이로 지정했다.

+ 높이의 범위는 1~100이므로 100보다 높으면 그냥 100을 저장해주었다.

 

그렇게 저장된 높이만큼 반복문을 돌면서 매 높이때마다 영역을 구해주고, 그 영역 count중 최대인 것을 출력해주면 된다. (매 높이마다 bfs를 수행해야하기 때문에 check배열을 초기화해주었다.)

 

탐색 조건에서 key보다 높은 영역을 탐색하는 BFS2함수를 만들었고 영역 중 침수되지 않는 영역만 탐색을 하게 된다.

 

마지막으로 아무 지역도 물에 잠기지 않을 수 있다는 조건을 보아서

최종 resultMax값이 0이면 1을 출력하게 했다.