C++ / 2468 / 안전 영역 ( 깊이 우선 탐색 )

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

문제 요약

어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수입니다. 예를 들어, 다음은 N = 5인 지역의 높이정보입니다.

 

이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 합니다. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같습니다.

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말합니다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 됩니다.

 

또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인 할 수 있습니다.

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 됩니다.

위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있습니다.

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

문제 풀이

1. 땅을 입력 받습니다.

2. 비는 -1로 초기화 합니다.

3. 비가 올 수 있는 최대치 ( 100 이하 ) 까지 비를 증가시키며 탐색합니다. 

4. dfs 탐색을 하는데 현재 비보다 높은 지역이면 탐색을 시작하고 탐색 종료시 개수를 셉니다.

5. 이전 개수보다 현재 개수가 더 클 경우 정답을 저장할 변수에 저장합니다.

6. 땅이 비에 다 잠겨버리면 반복문을 멈춥니다.

7. 정답을 저장한 변수를 출력합니다.

주의할 점

아무 지역도 물에  잠기지  않을 수도 있다는 사실을 기억해야합니다.

저는 땅이 1일 경우를 생각 못하고 비의 양을 0으로 시작 하여 틀렸었습니다.

-1로 해주면 땅이 1일 경우도 체크 할 수 있어서 정답이 됩니다.

코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

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

bool visit[101][101];
vector<vector<int>>v;

// 1인 경우 체크하기 위해 -1
int n, rain = -1;
int  cnt = 0;
int ret = 0;



void dfs(int y, int x)
{
	visit[y][x] = true;
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (nx >= n || nx < 0 || ny >= n || ny < 0)
		{
			continue;
		}
		if (visit[ny][nx])
		{
			continue;
		}
		// 비 보다 높은 지역만 탐색
		if (v[ny][nx] > rain)
		{
			dfs(ny, nx);
		}
	}
}

int main()
{
	cin >> n;
	v.resize(n, vector<int>(n));

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

	// 비 최대치 까지
	while (rain <= 100)
	{
		fill(&visit[0][0], &visit[0][0] + 101 * 101, false);
		rain++;
		ret = max(cnt, ret);
		cnt = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (!visit[j][i] && v[j][i] > rain)
				{
					dfs(j, i);
					cnt++;
				}
			}
		}
        // 비에 다 잠겨버리면 break
		if (cnt == 0)
		{
			break;
		}
	}

	cout << ret;
	return 0;
}

반응형

예제 1

5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

결과 1

예제 2

7
9 9 9 9 9 9 9
9 2 1 2 1 2 9
9 1 8 7 8 1 9
9 2 7 9 7 2 9
9 1 8 7 8 1 9
9 2 1 2 1 2 9
9 9 9 9 9 9 9

 

결과 2