[백준] 2580번 스도쿠

2580번: 스도쿠

입력을 받을 때 0인 것의 위치를 emptyLocation이라는 벡터에 집어넣는다.

그리고 1부터 9까지의 수로 emptyLocation.size() 만큼의 중복순열을 구한다.

check 함수는 숫자를 배치하려고 하는 위치에 그 값을 집어넣는 것이 바람직한지 체크해서 true나 false를 리턴해주는 함수이다.

#include <iostream>
#include <tuple>
#include <vector>
using namespace std;

int sudoku[9][9];
bool flag = false;
bool check(int row, int col, int value) {
	for (int i = 0; i < 9; i++) { //row번째 가로줄, col번째 세로줄에 value와 같은 값이 있는지 체크
		if (sudoku[row][i] == value || sudoku[i][col] == value)
			return false;
	}
	//(row, col)이 몇 번째 사각형에 속하는지 알아보고 그 사각형에 value와 같은 값이 있는지 체크
	int recRow = row / 3;
	int recCol = col / 3;
	for (int i = recRow * 3; i < recRow * 3 + 3; i++) {
		for (int j = recCol * 3; j < recCol * 3 + 3; j++) {
			if (sudoku[i][j] == value)
				return false;
		}
	}
	return true;
}

void select(int* result, vector<pair<int, int>> emptyLocation, int num) {
	if (num == emptyLocation.size()) {

		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << sudoku[i][j] << " ";
			}
			cout << endl;
		}
		flag = true;
		return;
	}

	for (int i = 1; i <= 9; i++) {
		if (check(emptyLocation[num].first, emptyLocation[num].second, i) && !flag) {
			result[num] = i;
			sudoku[emptyLocation[num].first][emptyLocation[num].second] = i;
			select(result, emptyLocation, num + 1);
			sudoku[emptyLocation[num].first][emptyLocation[num].second] = 0;
		}
		if (flag) {
			return;
		}
	}
}

int main() {
	vector<pair<int, int>> emptyLocation;
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> sudoku[i][j];
			if (sudoku[i][j] == 0) {
				emptyLocation.push_back(make_pair(i, j));
			}
		}
	}
	int count = emptyLocation.size();
	int* result = new int[count];
	select(result, emptyLocation, 0);

	return 0;
}