BOJ 2580 - 스도쿠

• 9X9 크기의 스도쿠를 푸는 문제이다.

문제 풀이

• 풀어야 하는 곳들을 저장해놓고 그 순서를 따라서 dfs를 돌리면 된다.

소스코드

#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;

int sd[9][9];
vi vl;

int check(int ci, int cj, int v);
int make_pq(){
	for(int i=0;i<9;i++) for(int j=0;j<9;j++){
		if(sd[i][j]) continue;
		vl.push_back(i*10+j);
	}
	if(vl.empty()) return 0;
	return 1;
}
int f(int idx);

int main()
{
	string s;
	for(int i=0;i<9;i++){
		int jidx=0;
		getline(cin, s, '\n');
		while(s=="") getline(cin, s, '\n');
		for(int j=0;j<s.length();j++) if(s[j]!=' ') sd[i][jidx++]=s[j]-48;
	}
	if(make_pq()) f(0);
	s.clear();
	for(int i=0;i<9;i++){
		for(int j=0;j<9;j++){
			s.push_back(sd[i][j]+'0');
			s.push_back(' ');
		}
		s.push_back('\n');
	}
	cout<<s;
}

int check(int ci, int cj, int v){
	for(int i=0;i<9;i++){
		if(sd[ci][i]==v) return 0;
		if(sd[i][cj]==v) return 0;
	}
	for(int i=ci/3*3;i<(ci/3+1)*3;i++) for(int j=cj/3*3;j<(cj/3+1)*3;j++)
		if(sd[i][j]==v) return 0;
	return 1;
}

int f(int idx){
	int ci=vl[idx]/10, cj=vl[idx]%10;
	for(int i=1;i<10;i++){
		if(check(ci, cj, i)){
			sd[ci][cj]=i;
			if(idx+1==vl.size()) return 1;
			if(f(idx+1)) return 1;
		}
		sd[ci][cj]=0;
	}
	return 0;
}

풀고나서

• 입력이 작기 때문에 그냥 0인 원소들만 뽑아서 [1, 9] 집어넣으면서 테스트하면 대충 O(N^(N^2))이다. (N=10)
  커팅을 하려고 단서가 가장 많은 원소들 순으로 정렬해서 풀려고 했다.(탐색하는 너비가 작아지기 때문) 하지만 정렬하는 과정에서 N^2가 필요하고 탐색할 때마다 N^2의 비용이 들어 결과적으로 O((N^2+N)^(N^2))를 만들어내고 몇 번 TLE가 났다.

• 54번째 줄을 if문 위로 옮겨서 check(ci, cj)를 호출하면 시간초과가 난다. 시간복잡도가 같아도 TLE가 났었다.(check 함수에서 벡터에 각 숫자 개수 저장하면서 2넘으면 0 반환하는 구조로 만들었었다.)