글 읽기 - C++ 틀린것 질문드립니다. (시도한 반례 포함)

totok682 4년 전 0

제가 짠 코드의 알고리즘은 다음과 같습니다.

매 테스트 케이스마다 InitArray()함수를 통해 배추가 심어져있는 배열 (cabbage)와 방문을 확인하는 배열 (visit)을 초기화합니다.
2중 반복문을 통해 배추가 심어져있는지 방문하는지 확인하는 함수 IsCabbage()를 호출합니다.
방문하지 않았고 배추가 심어져있다면 좌, 우, 아래에도 IsCabbage() 함수를 호출하여 탐색합니다(DFS)
IsCabbage가 True일때 Count를 올리고(붙어있는 배추가 있어도 한번만 Count됨) 마지막에 Count의 숫자를 출력합니다.

그리고 제가 시도한 테스트 케이스는 코드 아래에 첨부하겠습니다!

도와주시면 감사하겠습니다 ㅠㅠ

#include <iostream>
#include <vector>

using namespace std;

const int max_m = 50;
const int max_n = 50;

int M, N, K;

bool cabbage[max_n][max_m];
bool visit[max_n][max_m];

void PrintVisit()
{
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < M; x++)
		{
			if (visit[y][x])
				cout << 1;
			else
				cout << 0;
		}
		cout << '\n';
	}
	cout << '\n';
}

void InitArray()
{
	for (int y = 0; y < max_n; y++)
		for (int x = 0; x < max_m; x++)
		{
			cabbage[y][x] = false;
			visit[y][x] = false;
		}
}

bool IsCabbage(int y, int x)
{
	bool is_cabbage = false;
	if (cabbage[y][x] && !visit[y][x])
	{
		is_cabbage = true;
		visit[y][x] = true;

		if (x > 0)
			IsCabbage(y, x - 1);
		if (x < M - 1)
			IsCabbage(y, x + 1);
		if (y < N - 1)
			IsCabbage(y + 1, x);
	}
	
	return is_cabbage;
}

int CountWorms()
{
	int count = 0;
	for(int y=0; y < N; y++)
		for (int x = 0; x < M; x++)
		{
			if (IsCabbage(y, x))
			{
				count++;
				//PrintVisit();
			}
		}
	return count;
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		cin >> M >> N >> K;
		InitArray();
		for (int i = 0; i < K; i++)
		{
			int X, Y;
			cin >> X >> Y;
			cabbage[Y][X] = true;
		}
		cout << CountWorms() << '\n';
	}
	return 0;
}


<시도한 테스트 케이스 >
    1
5 5 5
0 0
1 1
2 2
3 3
4 4

1
3 3 8
0 0
0 1
0 2
1 0
1 2
2 0
2 1
2 2

1
50 50 4
0 0
49 0
0 49
49 49

1
1 3 1
0 2

1
10 10 2
9 5
0 6

2
3 2 2
0 1
2 1
3 3 1
0 0

2
2 2 1
0 0
2 2 1
1 1

2
1 1 1
0 0
1 1 1
0 0

1 
3 2 5
0 0
0 1 
1 0
2 0
2 1

1
3 1 3
0 0
2 0
1 0

1
50 50 1
49 49

1
1 10 3
0 1
0 5
0 8

2
3 2 1
2 1
2 3 1
1 2

2
10 5 4
0 0
0 1
9 0
9 1
5 10 4
0 0
1 0
0 9
1 9

dyk777 4년 전 3

위쪽은 보지 않는 이유가 있나요?

totok682 4년 전 1

dyk777

0~n-1 순으로 열과 행을 차례대로 간다는 생각에 위는 탐색할 필요가 없다고 생각했었는데.. 아니였네요 ㅠㅠ

이렇게 생긴 배추밭이 있으면 오류가 나겠군요, 아래 반례도 첨부하겠습니다 감사합니다 ^ㅡ^

<배추밭 모양>

0000

0101

0111

1
4 3 5
1 1
3 1
1 2
2 2
3 2

output : 2
answer : 1

cdt416z 4년 전 0

감사합니다!! 저도 똑같은 오류 있었네요 ㅋㅋㅋㅋㅋㅋㅋ

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

문제

문제

출처

ICPC

C++ 틀린것 질문드립니다. (시도한 반례 포함)

totok682 4년 전 0

dyk777 4년 전 3

totok682 4년 전 1

dyk777

cdt416z 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말