글 읽기 - 스도쿠 문제입니다. (2580번문제) 시간초과..

cheng1230 4년 전 0

시간초과로 통과가 되지않습니다..

머리를 쥐어짜보았지만 시간을 어느부분에서 더 줄여야할지 모르겠습니다. .

조언주시면 감사하겠습니다. ㅠㅠㅠ

#include <iostream>
#include <vector>

using namespace std;

int sudoku[9][9] = { 0 };
int zerocnt = 0;
bool rowcheck(int x,int y) {

	bool check[10] = { 0 };
	int cnt = 0;
	for (int i = 0; i < 9; i++) {
		if (sudoku[x][i] != 0) {
			check[sudoku[x][i]] = 1;
			cnt++;
		}
	}
	if (cnt == 8) {
		
		for (int i = 0; i <= 9; i++) {
			if (check[i] == 0) sudoku[x][y] = i;
		}
		return 1;
	}
	return 0;
}

bool colcheck(int x, int y) {

	bool check[10] = { 0 };
	int cnt = 0;
	for (int i = 0; i < 9; i++) {
		if (sudoku[i][y] != 0) {
			check[sudoku[i][y]] = 1;
			cnt++;
		}
	}
	if (cnt == 8) {
		for (int i = 0; i <= 9; i++) {
			if (check[i] == 0) sudoku[x][y] = i;
		}
		return 1;
	}
	return 0;
}

bool blockcheck(int x, int y) {

	bool check[10] = { 0 };
	int cnt = 0;
	int row = x / 3, col = y / 3;
	row *= 3; col *= 3;

	for (int i = row; i<row + 3; i++) {
		for (int j = col; j<col + 3; j++) {
			if (sudoku[i][j] != 0) {
				check[sudoku[i][j]] = 1;
				cnt++;
			}
		}
	} 
	if (cnt == 8) {
		for (int i = 0; i <= 9; i++) {
			if (check[i] == 0) sudoku[x][y] = i;
		}
		return 1;
	}
	return 0;
}
int main() {
	
	int  tmp;
	vector<pair<int, int>> v;

	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> tmp;
			if (tmp == 0) {
				v.push_back(make_pair(i,j));
			}
			sudoku[i][j]=tmp;
		}
	}
	int success = 0;

	while (!v.empty()) {
		for (int i = 0; i < v.size(); i++) {
			success=rowcheck(v[i].first, v[i].second);
			if (success == 1) {
				v.erase(v.begin() + i);
				break;
			}
			success = colcheck(v[i].first, v[i].second);
			if (success == 1) {
				v.erase(v.begin() + i);
				break;
			}
			success = blockcheck(v[i].first, v[i].second);
			if (success == 1) {
				v.erase(v.begin() + i);
				break;
			}
		}
	}

	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			printf("%d ", sudoku[i][j]);
		}
		printf("\n");
	}
}

lickelon 4년 전 0

알고리즘 전체적인 문제입니다.

쉽게는 모든 위치가 0으로만 이루어진 테스트케이스가 입력 되었을 때,

정확하게는 입력된 0들이 서로 의존적이어서 해결되지 않는 경우에 임의의 값을 넣어보며 백트래킹을 통해 통과해야 하지만 해당 코드는 그렇지 않습니다.

lickelon 4년 전 1

간단한 예시입니다.

0 5 4 6 9 2 7 8
0 2 1 3 5 6 4 9
6 9 2 7 8 1 3 5
2 1 5 4 6 8 9 7
7 4 9 1 3 5 2 6
9 6 8 2 7 4 1 3
1 7 6 5 2 3 8 4
4 3 7 8 1 9 5 2
5 8 3 9 4 7 6 1

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

문제

문제

출처

ICPC

스도쿠 문제입니다. (2580번문제) 시간초과..

cheng1230 4년 전 0

lickelon 4년 전 0

lickelon 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말