백준 2580 : 스도쿠 - C++

 

예제와 다르게 대부분의 칸이 0으로 채워져 있는 경우도 테스트케이스에 존재합니다.

결국 모든 경우의 수를 따져보는 방식으로 접근해야 합니다.

 

입력 -

0 0 0 0 4 3 0 0 0
0 0 0 0 0 0 1 0 0
0 0 0 0 5 0 0 0 0
0 8 0 7 0 0 0 2 0
0 6 0 0 0 0 0 0 3
0 0 0 0 0 0 0 4 0
0 0 5 8 0 0 6 0 0
4 0 0 1 0 0 0 0 0
3 0 0 0 0 0 5 0 0

 

출력 - 

6 7 1 9 4 3 2 5 8
5 4 2 6 8 7 1 3 9
8 3 9 2 5 1 4 6 7
1 8 3 7 6 4 9 2 5
9 6 4 5 2 8 7 1 3
2 5 7 3 1 9 8 4 6
7 1 5 8 3 2 6 9 4
4 9 6 1 7 5 3 8 2
3 2 8 4 9 6 5 7 1

 

0이 표시된 칸에 1부터 9까지 하나씩 입력해보고, 정답이 아니라면 후퇴하는 백트래킹 기법을 활용합니다.

#include <iostream>
#include <vector>

using namespace std;

int sdq[9][9];
vector<pair<int, int>> zeroV;
int zeroN;
bool found; // 완성된 스도쿠를 찾았는지 유무

bool check(int key, int row, int col) {
	int baseRow = (row / 3) * 3;
	int baseCol = (col / 3) * 3;

	for (int i = 0; i < 9; ++i) {
		if (sdq[i][col] == key) return false;
		if (sdq[row][i] == key) return false;
	}
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			if (sdq[baseRow + i][baseCol + j] == key) return false;
		}
	}
	return true;
}

void sudoku(int idx) {
	if (idx == zeroN) {
		found = true;
		return;
	}

	int curRow = zeroV[idx].first;
	int curCol = zeroV[idx].second;

	for (int i = 1; i <= 9; ++i) {
		if (!check(i, curRow, curCol)) continue;
		sdq[curRow][curCol] = i;
		sudoku(idx + 1);
        // 스도쿠가 완성된 뒤에 재귀 트리의 상위로 올라가는 과정에서
        // 계속해서 for문을 돌지 못하도록 막아야 합니다. 이를 위해 found 변수를 사용합니다.
		if (found) return; 
	}

	sdq[curRow][curCol] = 0;
	return;
}

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	int tmp;
	for (int row = 0; row < 9; ++row) {
		for (int col = 0; col < 9; ++col) {
			cin >> tmp;
			sdq[row][col] = tmp;
			if (tmp == 0) {
				zeroV.push_back({ row, col });
			}
		}
	}

	zeroN = zeroV.size();
	sudoku(0);

	for (int row = 0; row < 9; ++row) {
		for (int col = 0; col < 9; ++col) {
			cout << sdq[row][col] << " ";
		}
		cout << "\n";
	}

	return 0;
}