글 읽기 - 어디서 틀리는지 잘 모르겠네요 ㅠㅠ 93%에서 틀렸다고 나옵니다..

park780172 5년 전 0

비가 안 올 경우도 처리했는데 코드 어느 부분이 틀렸는지 계속 93%에서 틀렸다고 나오네요..

아래는 테스트 케이스입니다!

---------------------

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
6

---------------------

2
1 2
2 2
1

---------------------

1 1

----------------------

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>

using namespace std;

int visit[101][101] = { 0, };
int region[101][101] = { 0, };

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

int N = 0;

int MIN = 987654321;
int MAX = -987654321;
int safe_Cnt = -987654321;
int Connected_Component = 1;

void beforeBFS(int m)
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (region[i][j] <= m) // 이하
			{
				region[i][j] = 0; // 물에 잠김 = 0
			}
		}
	}
}

void DFS(int start, int end)
{
	visit[start][end] = 1; // 방문 처리

	for (int i = 0; i < 4; i++)
	{
		int y = start + dy[i];
		int x = end + dx[i];

		if (y <= 0 || x <= 0 || y > N || x > N || region[y][x] == 0 || visit[y][x] == 1) continue;

		DFS(y, x);
	}
}

void DFS_search()
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (visit[i][j] == 0 && region[i][j] != 0)
			{
				++Connected_Component;

				DFS(i, j);
			}
		}
	}
}

int main(void)
{
	int a = 0, b = 0;

	scanf("%d\n", &N);

	for (int i = 1; i <= N; i++) // 세로
	{
		for (int j = 1; j <= N; j++) // 가로
		{
			scanf("%d", &region[i][j]);

			MIN = min(MIN, region[i][j]);
			MAX = max(MAX, region[i][j]);
		}
	}

	if (MIN == MAX)
	{
		printf("1\n");

		return 0;
	}

	for (int i = MIN; i <= MAX; i++)
	{
		Connected_Component = 1;

		memset(visit, 0, sizeof(visit));

		beforeBFS(i);

		for (a = 1; a <= N; a++)
		{
			for (b = 1; b <= N; b++)
			{
				if (region[a][b] != 0) break;
			}
		}

		DFS(a, b);

		DFS_search();
	
		safe_Cnt = max(safe_Cnt, Connected_Component);
	}

	printf("%d\n", safe_Cnt);

	return 0;
}

park780172 5년 전 0

오잉 아래 코드로 바꾸니까 맞다고 뜨긴 뜨는데,

위에 코드는 안 되는지 잘 모르겠네요 ㅋㅋㅋ 분명 같은 접근법이고 연결 요소 개수 구하는 것은 똑같은데..

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>

using namespace std;

int visit[101][101] = { 0, };
int region[101][101] = { 0, };

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

int N = 0;

int MIN = 987654321;
int MAX = -987654321;
int safe_Cnt = -987654321;
int Connected_Component = 1;

void beforeBFS(int m)
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (region[i][j] <= m) // 이하
			{
				region[i][j] = 0; // 물에 잠김 = 0
			}
		}
	}
}

void DFS(int start, int end)
{
	visit[start][end] = 1; // 방문 처리

	for (int i = 0; i < 4; i++)
	{
		int y = start + dy[i];
		int x = end + dx[i];

		if (y <= 0 || x <= 0 || y > N || x > N || region[y][x] == 0 || visit[y][x] == 1) continue;

		DFS(y, x);
	}
}

int main(void)
{
	int a = 0, b = 0;

	scanf("%d\n", &N);

	for (int i = 1; i <= N; i++) // 세로
	{
		for (int j = 1; j <= N; j++) // 가로
		{
			scanf("%d", &region[i][j]);

			MIN = min(MIN, region[i][j]);
			MAX = max(MAX, region[i][j]);
		}
	}

	if (MIN == MAX)
	{
		printf("1\n");

		return 0;
	}

	for (int i = MIN; i <= MAX; i++)
	{
		Connected_Component = 0;

		memset(visit, 0, sizeof(visit));

		beforeBFS(i);

		for (a = 1; a <= N; a++)
		{
			for (b = 1; b <= N; b++)
			{
				if (region[a][b] != 0 && visit[a][b] == 0)
				{
					++Connected_Component;

					DFS(a, b);
				}
			}
		}

		safe_Cnt = max(safe_Cnt, Connected_Component);
	}

	printf("%d\n", safe_Cnt);

	return 0;
}

djm03178 5년 전 1

전자의 코드가 틀리는 이유는, 105번째 줄에서 break가 일어나면 108번째 줄로 나가는 것이 아니라 103번째 줄의 안쪽 루프만 탈출하기 때문에 결과적으로 루프를 나가지 못하고 또 돌기 때문입니다.

그래서 아예 이 루프들을 없애고, DFS(a, b) 같은 것도 할 필요 없이 Connected_Component를 0으로 초기화하고 바로 DFS_search를 돌려도 됩니다.

park780172 5년 전 0

억 감사합니다 !!! 덕분에 도움되었습니다 ㅎㅎ 제 코드가 더러워서 봐주신 것만으로도 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디서 틀리는지 잘 모르겠네요 ㅠㅠ 93%에서 틀렸다고 나옵니다..

park780172 5년 전 0

park780172 5년 전 0

djm03178 5년 전 1

park780172 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말