글 읽기 - 2580번, C++ 질문합니다. (시간초과와 연관)

ajb8406 3년 전 0

코드에서의 변수 설정은 다음과 같습니다.

a: 스도쿠 판 (9*9 배열), v: 채워야할 칸의 좌표(pair의 벡터), w: 채운 칸의 좌표를 저장(백트래킹시 만약 안되면 다시 돌아가야 할 때 쓸 정보)

코드에서의 함수는 다음과 같이 설정했습니다.

crit: a[k][l]에 m이 들어갈 수 있으면 true 아니면 false 반환

sudoku: v의 끝 부터 crit이 true인 i값을 for문으로 집어넣고 스도쿠판 재설정, v, w 재설정 후 다시 재귀.

만약 crit이 다 false라면 전에 집어넣은 가정들이 오류이므로 w를 이용하여 백트래킹.

문제점: 제가 생각하는 시간초과의 원인은 스도쿠 판이 한번 완성되면 바로 함수를 종료하고 싶은데 그렇지 않고 for문을 끝까지 돌아서 가장 마지막으로 나올 수 있는 답안을 내기 때문인 것 같은데요.

이를 해결할 좋을 방법이 없을까요?

(코드를 배운지 얼마 되지않아 지저분하게 코드를 쓴 점 양해 부탁드립니다..)

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//a에서 (k,l)에 m이 들어갈 수 있는지
int b[10] = { 0, };
vector<pair<int, int>> w;
bool crit(int a[][9], int k, int l, int m)
{
	for (int i = 0; i < 9; i++)
	{
		b[a[k][i]]++;
		b[a[i][l]]++;
	}
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			b[a[3*(k / 3) +i][3*(l / 3)+j]]++;
		}
	}
	if (b[m] == 0)
	{
		fill(b, b + 10, 0);
		return true;
	}
	else
	{
		fill(b, b + 10, 0);
		return false;
	}
}

void sudoku(int a[][9], vector<pair<int,int>> &v)
{
	if (v.size() == 0) return;
	int k, l;
	k = v.back().first;
	l = v.back().second;
	for (int i = 1; i <= 9; i++) {
		if (crit(a, k, l, i)) {
			a[k][l] = i;
			v.pop_back();
			w.push_back(make_pair(k, l));
			sudoku(a, v);
		}
		if (v.size() == 0) return;
	}
	if (a[k][l] == 0)
	{
		v.push_back(make_pair(w.back().first, w.back().second));
		a[w.back().first][w.back().second] = 0;
		//그러니까 r번째가 안되는 지점인데 r+1에서는 다 됨 근데 안되는
		//이유는 r+2번째라면 이런 식으로 작성을 해야함.
		w.pop_back();
		return;
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int a[9][9];
	vector<pair<int, int>> v;
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cin >> a[i][j];
			if (a[i][j] == 0)
			{
				v.push_back(make_pair(i,j));
			}
		}
	}
	sudoku(a, v);
	
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cout << a[i][j] << ' ';
		}
		cout << '\n';
	}
}

ajb8406 3년 전 0

지금 보시면 코드에 v.empty()인데도 for문이 헛돌지않습니까?

그런걸 보고 시간낭비가 되는겁니다. 아시겠어요?

그런걸 수정하면 좀 발전할 가능성이 있어보입니다.

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