[baekjoon 2239] 스도쿠 (완전탐색, 백트래킹) (C++)

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

2239번: 스도쿠

 

말 그대로 9X9의 스도쿠 판의 빈칸을 채우는 문제이다.

처음에는 이걸 어떻게 알고 풀지?라는 생각이 들었는데 9x9의 작은 사이즈로, N-Queen문제처럼 완전 탐색으로 다 돌려보면 되겠다고 생각이 들었다.

 

스도쿠의 규칙으로는 세로줄, 가로줄, 9개의 작은 사각형 중 하나에 1~9까지 채워야 하고, 중복된 숫자가 있으면 안 된다.

 

따라서 해당 범위에 맞게 체크 함수 3개를 만들어줬고, 빈칸을 채우는 것은 백트래킹으로 구현했다.

 

그리고, 스도쿠 판을 완성하게 된다면 출력 후 프로그램을 종료시켜야 한다. 그냥 return 할 경우, 스도쿠 판이 만들어지는 경우는 여러 가지이므로 출력 초과가 나올 것이다.

exit(0)을 사용해줬다.

 

나의 경우, 처음에는 재귀적으로 진행하되

x와 y 좌표를 가지고 진행 + 이미 중복된 숫자가 있어서 1~9까지 채우지 못하는 경우 return으로 true, false를 했는데 괜히 복잡하게 접근했다.

x와 y 좌표를 가지고 갈 필요 없이 처음부터 빈칸만 vector에 저장해줬고, true/false는 필요 없이 그냥 백트래킹을 하면 되는 것이었다.

실패한 경우, 아마 함수가 종료돼서 다시 돌아올 텐데 그때 백트래킹으로 좌표를 0으로 바꿔주고 다음 숫자부터 다시 진행하면 된다.

0으로 바꿔주지 않는다면, 배열 체크 시 숫자가 겹쳐서 정상 진행이 되지 않는다.

 

#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> pii;
string s;
vector<pii> empty_space;
int arr[10][10];

bool rowCheck(int row, int num) {
	for (int i = 0; i < 9; i++) {
		if (arr[row][i] == num)
			return false;
	}
	return true;
}

bool colCheck(int col, int num) {
	for (int i = 0; i < 9; i++) {
		if (arr[i][col] == num)
			return false;
	}
	return true;
}

bool squareCheck(int row, int col, int num) {
	int x = row / 3 * 3;
	int y = col / 3 * 3;
	for (int i = x; i < x + 3; i++) {
		for (int j = y; j < y + 3; j++) {
			if (arr[i][j] == num)
				return false;
		}
	}
	return true;
}

void sudoku(int pos) {
	if (pos == empty_space.size()){
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << arr[i][j];
			}
			cout << "\n";
		}
		exit(0); // 종료
	}
	
	int x = empty_space[pos].first;
	int y = empty_space[pos].second;

	for (int num = 1; num <= 9; num++) {
		if (rowCheck(x, num) && colCheck(y, num) && squareCheck(x, y, num)) {
			arr[x][y] = num;
			sudoku(pos + 1);
			arr[x][y] = 0; // 백트래킹을 위해서, 0으로 바꾸지 않는다면 계속 남아 있어서 다른 check에 영향을 끼친다.
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	for (int i = 0; i < 9; i++) {
		cin >> s;
		for (int j = 0; j < 9; j++) {
			arr[i][j] = s[j] - '0';
			if (arr[i][j] == 0)
				empty_space.push_back(make_pair(i, j));
		}
	}

	sudoku(0);

}