백준-2468 안전영역

1. 안전영역(DFS)

이 문제 또한 DFS를 활용하여 깊이 탐색을 하는 문제였다. 

앞서 문제와 한 가지 다른점은 앞서 유기농 배추 문제는 모든 배열의 값이 0아니면 1이 들어가서 바로 dfs를 탐색할 수 있었던 반면에 이 문제에서는 각 배열마다 다른 높이가 존재해서 높이를 비교하면서 가야한다는 점이 있었다. 

하지만 메모리 적으로 여유가 있어 나는 먼저 침수 높이d와 비교해 더 낮은 지대를 1의 값으로 갖는 비교 배열을 만들어준 후 앞선 유기농 배추 문제와 같이 dfs를 실행해주었다. 

dfs함수에서는 우선적으로 방문 배열을 1로 표시해주어야 하는 것이 중요하다는 것을 명심하자.

 

다음은 내가 문제를 푼 코드이다. 

#include<iostream>
#include<algorithm>
#include <tuple>
using namespace std;
int n;// 배열의 크기 가로 세로
int b[101][101];// 실제 map
int e[101][101]; 
int visited[101][101]; // 방문 배열
int dy[4] = {1, 0, -1, 0};
int dx[4] = {0,1,0,-1}; // 인덱스 배열
int ret = 1; // 연결된 컴포넌트 개수

int temp; 
void dfs(int y, int x) {
	visited[y][x]=1; // 방문 처리  
	for(int i = 0; i< 4; i ++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		if(ny < 0 || nx < 0 || ny >= n || nx >=  n) continue; // 경계조건 
		if(visited[ny][nx] == 0 && e[ny][nx] == 0) // 방문 안했고 생성 배열 구역이 안전구역이라면 dfs
		{
			dfs(ny, nx);
		}
	}
	return; 
} 
int main()
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n; // 가로 세로 길이 입력
	for( int i=0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			cin >> b[i][j];
		}
	} // 높이 입력
	
	for( int d=1; d < 101; d++){
		fill(&visited[0][0], &visited[0][0] + 101 * 101, 0);
		temp = 0;
		for(int i = 0; i < n; i ++){
			for(int j = 0; j< n; j++){
				if(e[i][j] == 1)continue;
				if(b[i][j] <= d) e[i][j] = 1;//1로 변환하는 배열 0이 안전 영역  
			}
		}
		for(int i = 0 ; i < n; i++){
			for(int j=0; j < n; j++){
				if(e[i][j] == 0 && !visited[i][j])
				{
					dfs(i, j);
					temp ++ ;
				}
			}
		}
		ret = max(ret, temp);
	}
	cout << ret << endl;
	return 0;
}

이 문제를 풀면서 새롭게 배운 c++의 함수는  max함수이다. 인자로 전달 받은 변수 중 가장 큰 것을 리턴한다. 

max(인수1, 인수2) ==  더 큰 인수 리턴