[BOJ] 백준 2468번 안전 영역

문제 링크 및 분석

[백준 / 2468] 안전 영역

2468번: 안전 영역

너비 우선 탐색 또는 깊이 우선 탐색을 이용해서 풀 수 있는 문제입니다. 문제를 풀 때 주의할 점은 비가 아예 오지 않을 수도 있다는 점입니다. 즉, 비의 높이는 0부터 모든 자연수일 수 있습니다. 저 같은 경우 입력된 숫자들 중에서 제일 큰 수까지 비가 오게 되면 모든 지역이 잠기기 때문에 제일 큰 수까지만 고려해주었습니다. 자세한 내용은 아래 코드 주석을 참고해주시기 바랍니다.

 

문제 소스 코드

#include <cstdio>
#include <algorithm>
#include <string.h>

using namespace std;

int n,maxHeight,maxnum;
bool check[101][101];
int saferand[101][101];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };

void dfs(int x, int y, int height) { // dfs 사용
	check[x][y] = true;
	for (int i = 0; i < 4; i++) {
		int nextx = x + dx[i];
		int nexty = y + dy[i];

		if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= n) continue;
        // 비가 온 높이 :  height, height 보다 높은 지역만 고려
		if (check[nextx][nexty] == false && saferand[nextx][nexty] > height) {
			dfs(nextx, nexty, height);
		}
	}
}
int main(void) {
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &saferand[i][j]);
			maxHeight = max(maxHeight, saferand[i][j]); // 입력된 숫자 중에서 가장 큰 숫자
		}
	}

	for (int k = 0; k <= maxHeight; k++) { // k: 비가 온 높이
		int cnt = 0;
		memset(check, false, sizeof(check));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (check[i][j] == false && saferand[i][j] > k) {
					dfs(i, j, k); // dfs를 거치게 되면 안전한 영역이 한 곳 증가
					cnt++;
				}
				
			}
		}
		maxnum = max(maxnum, cnt); // 안전한 영역 개수 최댓값
	}
	printf("%d\n",maxnum);
}

개발 환경 : Visual Studio 2019