[백준 BOJ][C++]2468번 안전 영역 풀이: DFS/BFS

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

2468번: 안전 영역

 

 각 지역의 높이 정보 map를 입력받을 때 최소, 최댓값을 minh와 maxh에 기록해둡니다. 

 

 그렇다면 검사해야할 높이는 minh <= h <= maxh 가 되겠지요!

 

 for문을 통해 이 사이에 있는 높이를 가지고 DFS를 진행합니다. 이때 높이가 바뀔때마다 방문 여부인 visit은 모두 false로, 안전 영역의 개수를 나타내는 cnt는 0으로 초기화 해주어야 합니다. 

 

 

 

#include<iostream>
#include<algorithm>
#include<cstdlib>

using namespace std;

int map[101][101];
bool visit[101][101] = { false, };
int n;
int maxh = 0;
int minh = 101;

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

void init_visit(){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++)
            visit[i][j]=false;
    }
}

void dfs(int x, int y, int h) {
    
    visit[y][x] = true;

	for (int i = 0; i < 4; i++) {
		int tx = x + dx[i];
		int ty = y + dy[i];

		if (tx < 0 || tx >= n || ty < 0 || ty >= n)
			continue;

		if (visit[ty][tx])
			continue;

		if (map[ty][tx] <= h)
			continue;

		dfs(tx, ty, h);
	}
}

int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	int cnt = 0;
	int ans = 1;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];

			maxh = max(maxh, map[i][j]);
			minh = min(minh, map[i][j]);
		}
	}

	for (int h = minh; h < maxh; h++) {

		cnt = 0;

		init_visit();

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!visit[i][j] && map[i][j] > h) {
					dfs(j, i, h);
					cnt++;
				}
			}
		}

		ans = max(ans, cnt);
	}


	cout << ans;


	return 0;
}