백준 2580번 스도쿠

https://www.acmicpc.net/problem/2580

2580번: 스도쿠

백트래킹 구현시 항상 search()함수를 void 타입으로 구현했는데, int형으로 수정되어 최초해가 나오면 바로 모든 search()함수가 종료되어 답이 바로 출력되는 소스코드. (linejin님이 수정)

#include<iostream>
#include<vector>
#include<utility>
using namespace std;
vector<pair<int, int>> v;
int sudoku[9][9];
int search(int cnt) {
	if (cnt >= v.size()) return 1;
	bool used_1[10];
	bool used_2[10];
	bool used_3[10];
	for (int i = 0; i <= 9; i++) { used_1[i] = false; used_2[i] = false; used_3[i] = false;}
	for (int i = 0; i < 9; i++) { //가로 세로 동시에 중복 체크
		if (sudoku[v[cnt].first][i])
		{
			if (!used_1[sudoku[v[cnt].first][i]])
				used_1[sudoku[v[cnt].first][i]] = true;
			else return 0;
		}
		if (sudoku[i][v[cnt].second])
		{
			if (!used_2[sudoku[i][v[cnt].second]])
				used_2[sudoku[i][v[cnt].second]] = true;
			else return 0;
		}
	}
	for (int i = v[cnt].first / 3 * 3; i < v[cnt].first / 3 * 3 + 3; i++) //정사각형 박스 중복 체크
		for (int j = v[cnt].second / 3 * 3; j < v[cnt].second / 3 * 3 + 3; j++)
			if (sudoku[i][j])
			{
				if (!used_3[sudoku[i][j]])
					used_3[sudoku[i][j]] = true;
				else return 0;
			}
	for (int i = 1; i <= 9; i++) { //유망한 숫자들 대입
		if (!used_1[i]&& !used_2[i]&& !used_3[i]) {
			sudoku[v[cnt].first][v[cnt].second] = i;
			if (search(cnt + 1))
				return 1;
			sudoku[v[cnt].first][v[cnt].second] = 0;
		}
	}
	return 0;
}
int main() {
	for (int i = 0; i < 9; i++) { //입력
		for (int j = 0; j < 9; j++) {
			int x;
			cin >> x;
			sudoku[i][j] = x;
			if (x == 0) v.push_back(make_pair(i, j)); //빈칸이라면 벡터에 좌표저장
		}
	}
	search(0);
	for (int i = 0; i < 9; i++) { //출력
		for (int j = 0; j < 9; j++) {
			if (j == 8) cout << sudoku[i][j] << "\n";
			else cout << sudoku[i][j] << " ";
		}
	}
	return 0;
}