[DFS] 백준 2468번, 안전영역

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

2468번: 안전 영역

백준 2468번, 안전영역에 대한 풀이이다.

문제는 링크를 참조해주기를 바란다.

---

문제해결

빗물의 높이가 주어지지 않는 상황에서 Input의 범위를 보고 빗물의 높이를 추정해야하는 것이 주의점이다.

영역의 탐색은 전체 map을 순회하며 visit되지 않은 구역을 Dfs로 탐색하며 방문 표시를 하기로 하였다. 인접 연결된 지역은 하나의 지역으로 판단되므로 Dfs 호출시에 cnt를 올려주었다.

필자는 탐색을 수행하기전에 지역 높이의 최소값과 최대값을 구해 해당 범위에서만 탐색을 하였다. 탐색 범위를 좁게 하기 위해서이다. 단, 해당 경우로 할 시 답이 0이 나올 수 있는 예외 case가 있다. 해당 case는 모든 영역의 높이가 같을 경우이다.  따라서 0은 1로 치환해주었다. 또한 애초에 탐색전, visit배열에 빗물 높이보다 같거나 낮은 경우를 표시하였다. Dfs 확산시 visit 배열의 값을 보고 1이나(이미 방문) -1이면(방문필요없음) 확산할 필요가 없기 때문이다.

Dfs의 확산은 방문과 종료만 잘하면 되며 노드 방문시에 따로 해야할 작업은 없다.

 

예외 case를 보자. N이 3이고 모든 값이 1이라고 하면 최소높이, 최대 높이도 1이다. 따라서 물의 높이도 1로 판단된다. 그러나 해당 case의 경우에는 물에 잠기지 않을 경우가 최대 1이다. 때문에 예외처리를 추가하였다. (비가 안와서 빗물이 0일 수도 있지 않은가?)

 

물높이를 1부터 최대값까지 Dfs 수행할 수도 있으나 높이값이 굉장히 큰 수라면 timeout이 발생할 가능성이 있다. 때문에 최소값을 추가하여 수행속도를 높이고 예외 처리를 하기로 했다.

코드는 아래와 같다.

 

#include <stdio.h>
#define MAX (int)1e6

int N;
int map[100+10][100+10];
int visit[100+10][100+10];
int minH=MAX;
int maxH=0;
int cnt;

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

void Input()
{
	scanf("%d", &N);
	
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<N; j++)
		{
			scanf("%d", &map[i][j]);
		}
	}
}

void FindHeight()
{
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<N; j++)
		{
			if(map[i][j]>maxH) maxH = map[i][j];
			if(map[i][j]<minH) minH = map[i][j];
		}
	}
}

void MakeMap(int h)
{
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<N; j++)
		{
			if(map[i][j]<=h) visit[i][j]=-1;
		}
	}
}

void Initvisit()
{
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<N; j++)
		{
			visit[i][j]=0;
		}
	}
}

void Dfs(int x, int y)
{
	if(visit[x][y]!=0)
	{
		return;
	}
	
	visit[x][y]=1;
	
	for(int i=0; i<4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		
		if(0>nx || nx>N-1 || 0>ny || ny>N-1) continue;
		if(visit[nx][ny]!=0) continue;
		Dfs(nx,ny);
	}
}


int main() {
	int ans=-1;
	Input();
	FindHeight();
	//printf("%d %d", minH, maxH);
	
	for(int i=minH; i<=maxH; i++) //빗물의 높이는 minH~maxH, i는 빗물의 범위
	{
		cnt=0;
		Initvisit();
		//map만들기, map은 보존해야하기 때문에
		MakeMap(i);
		
		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++)
			{
				if(visit[i][j]==0)
				{
					cnt++;
					Dfs(i,j);
				}
			}
		}
		
		if(cnt >= ans) ans = cnt;
	}
	
	if(ans==0) ans=1;
	printf("%d", ans);
	return 0;
}