백준 2468: 안전 영역

문제 요약

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

문제 분류

• 그래프 이론
• 브루트포스 알고리즘
• 그래프 탐색
• BFS
• DFS

문제 풀이

단순히 0과 1을 비교하는 것이 아닌, 1부터 최대 높이까지 탐색하면서 구역의 개수를 세는 문제이다.

높이를 k라고 하고, 탐색하면 되는데, 탐색할 때마다 visited배열을 초기화했다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int ary[100][100], n;
bool visited[100][100];

void dfs(int i, int j, int k) {
	visited[i][j] = true;
	if (i < n - 1)
		if ((ary[i + 1][j] >= k) && !visited[i + 1][j]) dfs(i + 1, j, k);
	if (i > 0)
		if ((ary[i - 1][j] >= k) && !visited[i - 1][j]) dfs(i - 1, j, k);
	if (j < n - 1)
		if ((ary[i][j + 1] >= k) && !visited[i][j + 1]) dfs(i, j + 1, k);
	if (j > 0)
		if ((ary[i][j - 1] >= k) && !visited[i][j - 1]) dfs(i, j - 1, k);
}


int main()
{
	int max = 0, cnt, res = 0;
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &ary[i][j]);
			if (max < ary[i][j]) max = ary[i][j];
		}
	}

	for (int k = 1; k <= max; k++) {
		cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++)
				visited[i][j] = false;
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!visited[i][j]) {
					if (ary[i][j] >= k) {
						dfs(i, j, k);
						cnt++;
					}
					else visited[i][j] = true;
				}
			}
		}
		if (cnt > res) res = cnt;
	}
	printf("%d", res);

	return 0;
}