[BOJ/C++] 2468 안전 영역 : BFS

문제

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

풀이

최단 경로 응용한 문제!

문제에 "아무 지역도 물에 잠기지 않을 수도 있다."라는 말이 있는데 이거에 관한 처리를 해주지 않아 런타임 에러 났음

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

int N;
int map[100][100];
int copy_map[100][100];
int cnt[100][100];
bool visited[100][100];

int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

int search_max() {
	int max = 0;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] > max) {
				max = map[i][j];
			}
		}
	}

	return max;
}

void flood(int height) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] <= height) {
				copy_map[i][j] = 0;
			}
			else {
				copy_map[i][j] = 1;
			}
		}
	}
}

void bfs(int x, int y) {
	queue<pair<int, int>> q;

	visited[x][y] = true;
	cnt[x][y]++;
	q.push({ x,y });

	while (!q.empty()) {
		int xx = q.front().first;
		int yy = q.front().second;

		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = xx + dx[i];
			int ny = yy + dy[i];

			if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny] && copy_map[nx][ny] == 1) {
				visited[nx][ny] = true;
				cnt[nx][ny] = cnt[xx][yy] + 1;
				q.push({ nx,ny });
			}
		}
	}
}

void reflect() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (cnt[i][j] > 0) {
				copy_map[i][j] = 0;
				cnt[i][j] = 0;
			}
		}
	}
}

int main() {
	vector<int> ans;

	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
		}
	}

	int max = search_max();
	for (int k = 1; k < max; k++) {
		flood(k);

		int area_cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (copy_map[i][j] == 1) {
					bfs(i, j);
					area_cnt++;
					reflect();
				}
			}
		}
		ans.push_back(area_cnt);

		memset(copy_map, 0, sizeof(copy_map));
		memset(cnt, 0, sizeof(cnt));
		memset(visited, false, sizeof(visited));
	}

	if (ans.size() == 0) { //아무 지역도 잠기지 않는 경우
		ans.push_back(1);
	}
	cout << *max_element(ans.begin(), ans.end());

	return 0;
}