글 읽기 - 도저히 어디가 틀렸는지 모르겠어요.

excalet007 4년 전 0

예제문제와 모두 0인 케이스 잘 작동하는데. 제출하면 자꾸 틀렸다고 뜨네요. 무엇이 문제인지 반나절 고민해도 안풀려요..ㅠㅠ 도와주세요

#include <iostream>

using namespace std;

const int N = 9;
int B[N][N];

//check[x][y] : is y in x
bool Row[N][N + 1];
bool Col[N][N + 1];
bool Sqr[N][N + 1];

//get th of square
int square(int r, int c)
{
	return(r / 3) * 3 + (c / 3);
}

//check row,col,sqr all have number
bool check(int r, int c, int n)
{
	if (Row[r][n] == false && Col[c][n] == false && Sqr[square(r, c)][n] == false)
		return true;
	else
		return false;
}

//set row,col,sqr same boolean
void set_check(int r, int c, int n, bool is)
{
	Row[r][n] = Col[c][n] = Sqr[square(r, c)][n] = is;
}

//recursive sudoku finding
bool sudoku(int th)
{
	//escape condition
	if (th == 81)
	{
		//print sudoku
		for(int r = 0; r<N; r++)
		{
			for (int c = 0; c < N; c++)
				cout << B[r][c] << " ";
			cout << "\n";
		}
		//exit recursive
		return true;
	}

	//get row,column
	int r = th / N;
	int c = th % N;

	//go next if number exits
	if (B[r][c] != 0)
		sudoku(th + 1);
	else
	{
		for(int n =1; n<=9; n++)
			if(check(r,c,n) == true)
			{
				//set temp for th+1
				set_check(r, c, n, true);
				B[r][c] = n;

				//recursive th+1
				if (sudoku(th + 1) == true)
					return true;
				
				//unset temp for th+1
				B[r][c] = 0;
				set_check(r, c, n, false);
			}
	}
	//escape condition3
	return false;
}


int main()
{
	//io speed
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	//input value
	for(int r = 0; r<N; r++)
		for(int c = 0; c <N; c++)
		{
			cin >> B[r][c];
			if (B[r][c] != 0)
				set_check(r, c, B[r][c], true);
		}

	//recursive start from 0th number
	sudoku(0);
    return 0;
}

excalet007 4년 전 0

앗!.... 바로 확인해보겠습니다 고맙습니다..!

excalet007 4년 전 0

물리조아님/ 혹시나 해서 전역변수 추가해서 한번만 출력되는것으로 해봤는데 똑같이 결과가 나오네요.

그리고 업로드한 코드 자체가 true -> true ->true 식으로 리턴되면서 답이여러개일지라도 처음 답을 찾으면 종료되게 됩니다 ㅠㅠ...어렵네요...

VS디버거로도 확인해보니 모두 0000인 케이스에 대해서도 단 한번만 작동합니다.

excalet007 4년 전 0

물리조아님/ 고맙습니다!! 덕분에 아이디어를 얻어서 풀 수 있었습니다.

chk를 제외했을때 return true/false하지 않는 부분이 어디인지 찾아보았더니

if (B[r][c] != 0) <--- 요기가 문제 59번째줄
sudoku(th + 1);

else{~~for()이부분은 굿}

if (B[r][c] != 0) { if(sudoku(th + 1) == true) return true; }

이렇게 바꾸어서 if,else 구문 모드 체크하게 하였더니 성공하였습니다. 고맙습니다~!!

excalet007 4년 전 0

하나더 추가해서 해봤는데요.

1.chk를 이용해서 처음에 탈출조건만 할경우

모든 if(sudoku(th+1))할필요 없이 sudoku(th+1)로 탐색만해도 아무 문제 없습니다.

2.전역변수 chk를 쓰기 싫다면

탈출조건,if/else구문 모두에서 빠짐없이 if(sudoku(th+1)) return 값을 줘서 빠져나올수 있게 해야합니다.

일장일단이 있지만, chk를 써서 한번만 체크하는것이 실수를 줄일수 있겠네요. 고맙습니다~!

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

문제

문제

출처

ICPC

도저히 어디가 틀렸는지 모르겠어요.

excalet007 4년 전 0

excalet007 4년 전 0

excalet007 4년 전 0

excalet007 4년 전 0

excalet007 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말