[백준 2468번 / C++] 안전 영역

DFS를 활용한 문제이다. 

 

N은 2이상 100이하이며 각 지역의 높이는 1이상 100이하 인것을 알아두자. 

 

먼저 지역의 높이를 나타내는 map을 입력 받고 check라는 배열도 h값이 변할 때마다 생성해주자. 

 

각 지역은 1부터 100이하이니 비가 차오른 높이도 그렇게 생각할 수 있지만 비가 아예 안 올 경우도 생각 해야한다. 

그러니, h의 범위는 0부터 100이라는 것을 주의하자. 

 

 

 

해당 그림을 보면서 어떻게 구현을 하였는지 확인하고 코드 주석을 보면서 이해해보자. 

#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;
int map[100][100], check[100][100], n;
int answer = INT_MIN;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 }; 
void dfs(int y, int x) {
	for (int i = 0; i < 4; i++) { //현재 x,y 좌표에서 상하좌우 살피기
		int nx = dx[i] + x; 
		int ny = dy[i] + y; 
		if (nx < 0 || nx >= n || ny < 0 || ny >= n)continue; //맵 이탈	
		if (check[ny][nx] == -1)continue;  //잠겨져 있을 때
		check[ny][nx] = -1; //check 맵 잠굼 처리
		dfs(ny, nx); 
	}
	return; 
}
int main() {
	cin >> n;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			cin>>map[y][x];
		}
	}
	for (int h = 0; h <= 100; h++) { //비가 안올 수 있으니 h이 0부터 시작
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < n; x++) {
				if (h >= map[y][x])check[y][x] = -1; //잠김
				else { 
					//check_area = true; 
					check[y][x] = 0; 
				}
			}
		}
		int cnt = 0; 
		for (int x = 0; x < n; x++) {
			for (int y = 0; y < n; y++) {
				if (check[y][x] == 0) {//잠기지 않은 영역 살피기
					check[y][x] = -1; 
					cnt++; 
					dfs(y, x); 
				}
			}
		}
		answer = max(answer, cnt); 
	}
	cout << answer; 
	return 0; 
}

 

2468번: 안전 영역