[BOJ] #2468 _ 안전 영역

[안전 영역] https://www.acmicpc.net/problem/2468

2468번: 안전 영역

bfs나 dfs를 이용하여 안전한 구역의 개수를 세는 문제이다.

 

[ 소스 코드 ]

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 100

using namespace std;

int dx[4] = { 0, 0, -1, 1 }, dy[4] = { -1, 1, 0, 0 };
int N, high, result = 1;
vector<vector<int> > town;

void solve(int sink);
int main() {
	scanf("%d", &N); //input
	town.assign(N, vector<int>(N, 0));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &town[i][j]);
			if (high < town[i][j]) high = town[i][j];
		}
	}

	for (int i = 1; i <= high; i++) solve(i); //use bfs

	printf("%d\n", result);

	return 0;
}

void solve(int sink) {
	queue <pair<int, int> > q;
	pair<int, int> tmp;
	vector<vector<int> > check(N, vector<int>(N, 0));
	int x, y, count = 0;

	for (int i = 0; i < N; i++) { //check sinked place
		for (int j = 0; j < N; j++) {
			if (town[i][j] <= sink) check[i][j] = 1;
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (check[i][j] == 1) continue;
			q.push(make_pair(i, j));
			check[i][j] = 1;
			count++;
			while (!q.empty()) {
				tmp = q.front();
				q.pop();

				for (int k = 0; k < 4; k++) {
					x = tmp.second + dx[k];
					y = tmp.first + dy[k];

					if (x < 0 || y < 0 || x >= N || y >= N) continue;
					if (check[y][x] == 1) continue;
					q.push(make_pair(y, x));
					check[y][x] = 1;
				}
			}
		}
	}
	result = max(result, count);
}