글 읽기 - 1012번 c++코드 질문입니다.

gogosing 2년 전 0

문제에 나온 테스트 케이스 2개는 잘 나오는데 제출 시 틀렸다고 나옵니다

반례가 있을까요 ? 도와주세요 ㅠㅠ

#include <iostream>
#include <vector>

using namespace std;

#define MAX_LEN 51
int dx[4] = { -1,0,0,1 };
int dy[4] = { 0,1,-1,0 };
int arr[MAX_LEN][MAX_LEN] = {0,};
int visit[MAX_LEN][MAX_LEN] = { 0, };
int result = 0;
int xside;
int yside;
vector<int> total_result;


void dfs(int x, int y)
{

	visit[x][y] = true;
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || nx > xside || ny < 0 || ny > yside) continue ;
		if (arr[nx][ny] == 1 && visit[nx][ny] == false)
			dfs(nx, ny);
	}
}

void initialize()
{
	for (int i = 0; i < xside; i++)
		for (int k = 0; k < yside; k++)
		{
			arr[i+1][k+1] = false;
		}
	result = 0;
}

int main()
{
	int testcase;
	cin >> testcase;
	for (int i = 0; i < testcase; i++)
	{
	
		int chu_num;
		cin >> xside >> yside >> chu_num;
		for (int k = 0; k < chu_num; k++)
		{
			int arr_x;
			int arr_y;
			cin >> arr_x >> arr_y;
			arr[arr_x+1][arr_y+1] = 1;
		}
		for (int a = 1; a <= xside; a++)
		{
			for (int b = 1; b <= yside; b++)
			{
				if (visit[a][b] == false && arr[a][b] == 1)
				{
					dfs(a, b);
					result++;

				}
			}
		}

		total_result.push_back(result);
		initialize();

	}
	for (int i = 0; i < total_result.size(); i++)
	{
		cout << total_result[i] << endl;
	}
}

palilo 2년 전 1

격자 범위를 [1, xside] * [1, yside]로 사용하는 것 같은데

그러면

if (nx < 0 || nx > xside || ny < 0 || ny > yside) continue ;

에서 0을 1로 바꿔야죠

dps2 2년 전 1

visit 배열을 초기화하고 있지 않으십니다.

arr초기화해주는 곳에서 visit 초기화하는 코드 추가했더니 맞았습니다 떴습니다.

dps2 2년 전 1

윗 댓글 남겨주신 분 저보다 고수이신데 제 생각을 조심스럽게 말씀드리자면

이 경우 index가 0인 곳이 0으로 패딩되어있다라고 생각하면 작동하는데 문제 없는 것 같습니다.

저 부분은 수정하지 않고 위에 언급한 visit 초기화만 했더니 맞았습니다가 떴습니다.

gogosing 2년 전 0

감사합니다 ㅎㅎ

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

문제

문제

출처

ICPC

1012번 c++코드 질문입니다.

gogosing 2년 전 0

palilo 2년 전 1

dps2 2년 전 1

dps2 2년 전 1

gogosing 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말