글 읽기 - 스도쿠 시간초과 질문입니다! ㅠㅠㅠ 고수님들 도와주세요!

pda_pro12 6년 전 0

시간초과가 떠버리는데 이유를 도무지 모르겠습니다...ㅠㅠㅠ 고수님들 도와주세요!

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
#pragma warning(disable:4996)
#define MAX_N 9
int ar[MAX_N][MAX_N]; bool row[MAX_N][10];   bool col[MAX_N][10];  bool square[MAX_N][10];

int sq(int x, int y) {
	return (x / 3) * 3 + y / 3;
}

void dfs(int z) {

	if (z == 81) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << ar[i][j] << " ";
			}
			cout << endl; 
		}
		return; 
	}

	int x = z / 9;   // 9칸이 다 차면 행이 증가하므로 /9를 취해준다. 
	int y = z % 9;    // 열은 퍼센테이지로 9를 넘는 경우가 생기면 안됨; 

	if (ar[x][y] != 0) {
		dfs(z + 1);
	}
	else {
		for (int i = 1; i <= 9; i++) {
			if (row[x][i] == false && col[y][i] == false && square[sq(x, y)][i] == false) {
				row[x][i] == true; col[y][i] == true;  square[sq(x, y)][i] == true;
				ar[x][y] = i; 
				dfs(z + 1);
				ar[x][y] = 0;
				row[x][i] == false; col[y][i] == false;  square[sq(x, y)][i] == false;
			}
		}
	}
	return; 
}
int main()
{
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> ar[i][j];
			if (ar[i][j] != 0) {
				row[i][ar[i][j]] = true;
				col[j][ar[i][j]] = true; 
				square[sq(i, j)][ar[i][j]] = true; 
			}
		}
	}

	dfs(0);

	return 0;
}

djm03178 6년 전 0

"스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다."

이 말은 답이 여럿 있는 판의 경우 하나만을 출력해야 하고, 모든 경우를 완전탐색하는 데에 걸리는 시간은 절대 보장되지 않는다는 것을 의미합니다. 하나를 찾으면 바로 탐색을 종료해야 하는데, 모든 답을 구할 때까지 완전탐색을 하니 시간이 오래 걸립니다.

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

문제

문제

출처

ICPC

스도쿠 시간초과 질문입니다! ㅠㅠㅠ 고수님들 도와주세요!

pda_pro12 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말