[BOJ2580] 스도쿠

 

백트래킹 연습문제로 적당한것같다.

 

 

 

 

2580번: 스도쿠

 

 

81%에서 시간 초과가 났다.

 

check 부분을 비효율적으로 짜서 그런건데 재귀되는 함수에서 배열을 너무 많이 생성한듯.

//81% 시간 초과
for (int i = 0; i < 9; i++) {
		visit_x[sdoku[x][i]] += 1;
		visit_y[sdoku[i][y]] += 1;
		if(sdoku[x][i]!=0)
			if (visit_x[sdoku[x][i]] > 1) 
				return false;
		if (sdoku[i][y] != 0)
			if (visit_y[sdoku[i][y]] > 1) 
				return false;
	}
	for (int i = (x / 3) * 3; i < (x / 3) * 3 + 3; i++) {
		for (int j = (y / 3) * 3; j < (y / 3) * 3 + 3; j++) {
			visit_xy[sdoku[i][j]] += 1;
			if(sdoku[i][j]!=0)
				if (visit_xy[sdoku[i][j]] > 1) 
					return false;
		}
	}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vii;
vii sdoku(9, vi(9, 0));
vector<pair<int, int>> blank;

void input() {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> sdoku[i][j];
			if (sdoku[i][j] == 0) {
				blank.push_back(make_pair(i, j));
			}
		}
	}
}

bool check(int x,int y,int value) {
	//수정된부분
	for (int i = 0; i < 9; i++) {
		if(sdoku[x][i]==value)
			return false;
		if (sdoku[i][y] == value)
			return false;
	}
	for (int i = (x / 3) * 3; i < (x / 3) * 3 + 3; i++) {
		for (int j = (y / 3) * 3; j < (y / 3) * 3 + 3; j++) {
			if(sdoku[i][j]==value)
				return false;
		}
	}
    //수정된부분 end
	return true;

}
void print() {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cout << sdoku[i][j] << " ";
		}
		cout << "\n";
	}
}
bool flag = 0;
void dfs(int N) {
	if (flag) return;
	if (N == blank.size()) {
		print();
		flag = 1;
		exit(0);
	}
	for (int i = 1; i < 10; i++) {
		if (check(blank[N].first, blank[N].second, i)) {
			sdoku[blank[N].first][blank[N].second]= i;
			dfs(N + 1);
            sdoku[blank[N].first][blank[N].second] = 0;
		}
	}
	
}

int main() {
	input();
	dfs(0);
	
}