글 읽기 - 스도쿠 질문입니다.

cubalys 6년 전 0

2580 스도쿠 문제와 같은 문제라고 생각했는데 2580번은 맞는데 이문제는 틀리네요

다른 부분은 정답이 여러개인 경우에 사전순으로 가장 앞서는 것을 출력하도록 하는 것인데

0의 위치가 가장 앞에있는 부분부터, 작은 수 먼저 채워가기 때문에

가장 먼저 찾는 경우의 수가 자연스럽게 사전순으로 가장 앞설 것이라고 생각했는데

제가 잘못 생각한 것일까요..?

#include <cstdio>
int map[10][10], jcheck[10][10], icheck[10][10], sqcheck[10][10], sqnum[10][10], zeroi[100], zeroj[100], zerop;
void F(int x){
	int ii = zeroi[x], jj = zeroj[x];
	if (x == zerop){
		for (int i = 1; i <= 9; i++){
			for (int j = 1; j <= 9; j++)
				printf("%d", map[i][j]);
			puts("");
		}
		return;
	}
	for (int i = 1; i <= 9; i++){
		if (!icheck[ii][i] && !jcheck[jj][i] && !sqcheck[sqnum[ii][jj]][i]){
			icheck[ii][i] = jcheck[jj][i] = sqcheck[sqnum[ii][jj]][i] = 1;
			map[ii][jj] = i;
			F(x + 1);
			map[ii][jj] = icheck[ii][i] = jcheck[jj][i] = sqcheck[sqnum[ii][jj]][i] = 0;
		}
	}
}
int main(){
	for (int i = 1; i <= 9; i++)
		for (int j = 1; j <= 9; j++)
			sqnum[i][j] = (j - 1) / 3 + (i - 1) / 3 * 3 + 1;
	for (int i = 1; i <= 9; i++){
		for (int j = 1; j <= 9; j++){
			scanf("%1d", &map[i][j]);
			if (map[i][j]){
				icheck[i][map[i][j]] = 1;
				jcheck[j][map[i][j]] = 1;
				sqcheck[sqnum[i][j]][map[i][j]] = 1;
			}
			else{
				zeroi[zerop] = i;
				zeroj[zerop++] = j;
			}
		}
	}
	F(0);
}

sgchoi5 6년 전 0

영문을 보니 TC 가 있다고 되어 있네요. 원문을 찾아보니 아래와 같이 TC 개수가 있었습니다. TC 개수 처리해서 제출해보니 틀렸습니다는 아니고, 시간초과네요..

2580 번 처리방식(완전탐색 + 백트래킹)으로 했는데.... 잘 되시나요?

1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

sgchoi5 6년 전 1

영문은 원문이라 TC 가 언급이 되어 있고, BOJ 에 적용할 때는 TC 없이 하나만 했나봐요.

2580 번 처리방식(완전탐색 + 백트래킹)에서 출력만 잘 되게 바꾸니 패스했습니다.. ^^;;

F() 함수 호출시에 한 번 출력후에 완전히 끝내도록 global 변수 하나 두시면 되겠네요.

cubalys 6년 전 0

감사합니다 덕분에 맞았습니다

그러고 보니 모든 경우를 다 출력하네요

2580번의 경우는 정답이 여러개인 테스트 케이스가 없었나봐요...

근데 왜 출력초과가 아닌 틀렸습니다 라고 나왔을까요? ㅋㅋ

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

문제

문제

출처

ICPC

스도쿠 질문입니다.

cubalys 6년 전 0

sgchoi5 6년 전 0

sgchoi5 6년 전 1

cubalys 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말