글 읽기 - 테스트 케이스는 잘 나오는데, 왜 틀렸을까요...? ㅠ ㅠ

kim031504 4년 전 0

최대 3개까지 가로 선을 그을 수 있다는 것을 전제 하에

전역으로 W 변수를 만들어 1부터 3까지 해서

각각에 대해 판단하였습니다.

물론 0인 경우는 초기에 판단하여 예외처리를 했구요!

테스트 케이스는 잘 나옵니다.

하지만 런타임 에러가 나네요 ㅠ

제 코드에 대한 자세한 설명은 주석으로 달아놨습니다!

도와주십쇼 ㅠㅠ

#include <iostream>


using namespace std;

int ladder[100][100]; // 초기 사다리 상태
int temp[100][100]; // 초기 상태에서부터 계속 덧칠해 나갈 것이므로 임시 배열!
int N, M, H;

// 추가해야 할 가로선 처음에 1부터 시작
int W = 1;

// 얘가 현재 해를 만족하는지 판단한다.
bool judge = false;

/*
	가로선이 다 놓인 상황에서
	한 열에 대한 조건을 만족하는지 검사하는 함수이다.
*/
bool go(int col)
{
	// 초기의 열의 값을 담는다.
	int copy = col;

	int row = 1;

	while (row != H)
	{
		if (temp[row][col] == 0)
		{
			row += 1;
		}
		else if (temp[row][col] == 1)
		{
			col += 1;
			row += 1;
		}
		else if (temp[row][col] == 2)
		{
			col -= 1;
			row += 1;
		}
	}

	if (temp[row][col] == 1)
		col += 1;
	else if (temp[row][col] == 2)
		col -= 1;


	// 최종적으로 초기 열과 같은가?
	if (col == copy)
		return true;
	else
		return false;
}

/*
	위의 go 함수를 이용해서 모든 열에 대한 최종 판단을 한다.
*/
bool JUDGE()
{
	int cnt = 0;

	for (int k = 1; k <= N; k++)
	{
		if (go(k))
		{
			cnt += 1;
		}
	}

	// 모든 열에 검증이 된 것이므로
	if (cnt == N)
	{
		return true;
	}

	return false;
}


// 사다리 만드는 경우
bool makeLadder(int cnt)
{
	if (judge)
	{
		return true;
	}

	// 1 ~ 3까지 만들 것이다.
	if (cnt == W)
	{
		// 모든 열에 검증이 된 것이므로
		if (JUDGE())
		{
			judge = true;
			return true;
		}
		else
			return false;
	}

	for (int i = 1; i <= H; i++)
	{
		for (int j = 1; j <= N-1; j++)
		{
			// 빈 곳 발견 즉시
			if (temp[i][j] == 0 && temp[i][j+1] == 0)
			{
				// 가로선 그어주고
				temp[i][j] = 1;
				temp[i][j + 1] = 2;

				// 검증 시작!
				makeLadder(cnt + 1);

				if (judge)
					return true;

				// 다시 허문다
				temp[i][j] = 0;
				temp[i][j + 1] = 0;
			}
		}
	}

	
}

int main()
{
	cin >> N >> M >> H;

	// 초기에 주어진 가로선의 정보 기입
	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;

		ladder[a][b] = 1;
		ladder[a][b + 1] = 2;
	}

	// 초기 상태에 대한 검증을 진행한다.
	for (int i = 1; i <= H; i++)
	{
		for (int j = 1; j <= N; j++)
			temp[i][j] = ladder[i][j];
	}

	if (JUDGE())
	{
		cout << 0 << '\n';
		return 0;
	}

	

	while (W <= 3)
	{
		for (int i = 1; i <= H; i++)
		{
			for (int j = 1; j <= N-1; j++)
			{
				// 가로선 그을 수 있는 곳 발견 즉시
				if (ladder[i][j] == 0 && ladder[i][j+1] == 0)
				{
					// 초기 사다리 상태 temp에 복사!
					for (int k = 1; k <= H; k++)
					{
						for (int l = 1; l <= N; l++)
						{
							temp[k][l] = ladder[k][l];
						}
					}

					// 해당 부분에 가로선 긋는다.
					temp[i][j] = 1;
					temp[i][j + 1] = 2;

					// 이미 가로선을 그은 상태이므로 cnt=1
					makeLadder(1);

					// 검증이 완료가 되어 전역 변수가 셋팅 된 순간 현재 W가 답이므로!
					if (judge)
					{
						cout << W << '\n';
						return 0;
					}
				}
			}
		}

		W += 1;
	}

	cout << -1 << '\n';

	return 0;
}

shj1504 4년 전 1

반례드립니다.

10 5 30
30 9
3 2
2 3
5 1
5 4

answer -1

kim031504 4년 전 0

우와! 두서없이 난잡하게 쓴 소스 읽어주셔서 감사해요!

그런데 주어진 테스트 케이스로 돌려봤는데,

답은 -1로 잘 나오네요 ㅠㅠ

답이 틀린게 아니라 런타임 에러라서

중간에 인덱스 오류 같은거 나나 찾아봐도 못 찾겠네요 ㄷㄷ;

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

문제

문제

출처

ICPC

테스트 케이스는 잘 나오는데, 왜 틀렸을까요...? ㅠ ㅠ

kim031504 4년 전 0

shj1504 4년 전 1

kim031504 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말