안전 영역

일단 문제 이해는 Connected Component문제이다.

안전영역의 최대 갯수를 구하는 문제인데

나는 배열 두개를 선언해서 하나는 원본(arr), 하나는 높이에 따라 0 또는 1로 바꿀 맵(temp)를 선언해서 반복문 내에서 temp는 0또는 1로 채우고 기존의 DFS함수를 그대로 사용을 했다.

코드는 아래와 같은데 계속 76%쯤에서 실패했다고 뜬다.

아마 PTC에서 한두개쯤 걸리는거같은데... 어느 부분이 잘 못됬는지 잘 모르겠다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define endl "\n"
#define MAX 101

int n;
int Max = -1;
int cnt = 0;
int arr[MAX][MAX];
int temp[MAX][MAX];
int visited[MAX][MAX];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {-1, 0, 1, 0};

bool Cango(int y, int x)
{
	if (y < 0 || y >= n || x < 0 || x >= n || temp[y][x] == 0) return false;
	return true;
}

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 (Cango(ny, nx) == false) continue;
		if (visited[ny][nx]) continue;
		DFS(ny, nx);
	}
}

void DFS_ALL()
{
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if (temp[i][j] == 0) continue;
			if (visited[i][j]) continue;
			DFS(i, j);
			++cnt;
		}
	}

	Max = max(Max, cnt);
	cnt = 0;
}

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 >> arr[i][j];

	for (int h = 1; h < 101; ++h)
	{
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
				if (arr[i][j] > h) temp[i][j] = 1;
		}

		DFS_ALL();

		memset(temp, 0, sizeof(temp));
		memset(visited, 0, sizeof(visited));
	}

	cout << Max << endl;

	return 0;
}

수업코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define endl "\n"
#define MAX 101

int n;
int ret = 1;
int cnt = 0;
int arr[MAX][MAX];
int temp[MAX][MAX];
int visited[MAX][MAX];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {-1, 0, 1, 0};

void DFS(int y, int x, int h)
{
	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] && arr[ny][nx] > h) DFS(ny, nx, h);
	}
}

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 >> arr[i][j];

	for (int h = 1; h < 101; ++h)
	{
		fill(&visited[0][0], &visited[0][0] + 101 * 101, 0);
		int cnt = 0;
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				if (arr[i][j] > h && !visited[i][j])
				{
					DFS(i, j, h);
					++cnt;
				}
			}
		}
		ret = max(ret, cnt);
	}

	cout << ret << endl;

	return 0;
}

내코드랑 거의 똑같은데 내가 작성한 코드에서 뭐가 문제인지 모르겠다.

일단 질문 올림.

답변

답변

결론

결로은 내가 문제의 뜻을 정확히 파악을 하지 못했다.

장마철이 비가 올 수도있고 안올 수도 있음. 그리고 문제의

노트를 보게되면은 아무 지역도 물이 잠기지 않을 수 있다라고하는데 이게 비가 안올 수도 있다는 말임.

즉 장마철이 비가 아예 안오는 경우를 제외를 하고 나는 높이가 1이상 100이하 인점에만 집중해서 빗물도 무조건 1이상이여야 하는줄알고 h = 1부터 시작해버렸음.

결론은 h = 0부터 시작할 수 있다라는 말임.

내 코드 수정

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define endl "\n"
#define MAX 101

int n;
int Max = -1;
int cnt = 0;
int arr[MAX][MAX];
int temp[MAX][MAX];
int visited[MAX][MAX];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {-1, 0, 1, 0};

bool Cango(int y, int x)
{
	if (y < 0 || y >= n || x < 0 || x >= n || temp[y][x] == 0) return false;
	return true;
}

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 (Cango(ny, nx) == false) continue;
		if (visited[ny][nx]) continue;
		DFS(ny, nx);
	}
}

void DFS_ALL()
{
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if (temp[i][j] == 0) continue;
			if (visited[i][j]) continue;
			DFS(i, j);
			++cnt;
		}
	}

	Max = max(Max, cnt);
	cnt = 0;
}

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 >> arr[i][j];

	for (int h = 0; h < 101; ++h)
	{
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
				if (arr[i][j] > h) temp[i][j] = 1;
		}

		DFS_ALL();

		memset(temp, 0, sizeof(temp));
		memset(visited, 0, sizeof(visited));
	}

	cout << Max << endl;

	return 0;
}

딱 h = 1에서 h = 0으로만 변경됨.