[백준 2580] 스도쿠

백트래킹으로 빈칸마다 들어갈 수 있는 수를 찾아 넣어주자.

그러다보면 빈칸임에도 불구하고 넣을 수 있는 숫자가 없는 경우가 있다.

이 경우엔 앞에서 잘못된 숫자가 들어간 것이기 때문에, 다시 뒤로 돌아가자.

 

\((x, y)\)번째 칸에 넣을 수를 찾는 방법은 1부터 9까지 돌면서

1. \(x\)번째 행에 어떤 수 \(n\)이 존재하는지
2. \(y\)번째 열에 어떤 수 \(n\)이 존재하는지
3. \(((x / 3), (y / 3))\)번 정사각형 안에 어떤 수 n이 존재하는지 (하단 그림 참조)

   

확인해주면 된다.

 

1. bool 배열로 구현

#include <bits/stdc++.h>
using namespace std;

int sudoku[9][9];
bool row[9][10]; // 행
bool col[9][10]; // 열
bool block[3][3][10]; // 3x3 정사각형
vector<pair<int, int>> blank; // 빈칸들의 좌표

void recur(int cur) {
	// 모든 칸이 채워졌다면 출력 후, exit(0)을 통해 바로 프로그램 종료
	if (blank.size() == cur) {
		for (int i = 0; i < 9; ++i) {
			for (int j = 0; j < 9; ++j) cout << sudoku[i][j] << ' ';
			cout << '\n';
		}
		exit(0);
	}
    
	int x = blank[cur].first;
	int y = blank[cur].second;

	for (int i = 1; i < 10; ++i) {
		// i라는 숫자가 현재 칸이 속한 행, 열, 3x3 정사각형 안에 존재하는 지 확인
		// 한 곳이라도 존재하면 다음 숫자로 넘어감
		if (row[x][i] || col[y][i] || block[x / 3][y / 3][i]) continue;

		// (x, y)에 i라는 숫자를 채워넣음
		row[x][i] = true;
		col[y][i] = true;
		block[x / 3][y / 3][i] = true;
		sudoku[x][y] = i;
        
		recur(cur + 1); // 다음 칸으로 넘어가기
		
		// 호출한 재귀함수가 리턴됐다는 것은, 현재 빈칸에 i라는 숫자가 들어가면 안된다는 의미
		// 다른 숫자를 채워넣기 위해, (x, y)에서 i라는 숫자를 제거
		row[x][i] = false;
		col[y][i] = false;
		block[x / 3][y / 3][i] = false;
		sudoku[x][y] = 0;
	}
}

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

	for (int i = 0; i < 9; ++i) for (int j = 0; j < 9; ++j) {
		cin >> sudoku[i][j];
		// 입력받은 수를 행, 열, 3x3 정사각형에 추가
		row[i][sudoku[i][j]] = true;
		col[j][sudoku[i][j]] = true;
		block[i / 3][j / 3][sudoku[i][j]] = true;

		if (sudoku[i][j] == 0) blank.push_back({ i, j });
	}

	recur(0);

	return 0;
}

 

2. 비트 연산으로 구현

#include <bits/stdc++.h>
using namespace std;

int sudoku[9][9];
int row[9];
int col[9];
int block[3][3];
vector<pair<int, int>> blank;

void recur(int cur) {

	if (blank.size() == cur) {
		for (int i = 0; i < 9; ++i) {
			for (int j = 0; j < 9; ++j) cout << sudoku[i][j] << ' ';
			cout << '\n';
		}
		exit(0);
	}
    
	int x = blank[cur].first;
	int y = blank[cur].second;

	for (int i = 1; i < 10; ++i) {
		int bit = (1 << i);

		if ((row[x] & bit) || (col[y] & bit) || (block[x / 3][y / 3] & bit)) continue;

		row[x] |= bit;
		col[y] |= bit;
		block[x / 3][y / 3] |= bit;
		sudoku[x][y] = i;
		recur(cur + 1);
		
		row[x] &= (~bit);
		col[y] &= (~bit);
		block[x / 3][y / 3] &= (~bit);
		sudoku[x][y] = 0;
	}
}

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

	for (int i = 0; i < 9; ++i) for (int j = 0; j < 9; ++j) {
		cin >> sudoku[i][j];
		row[i] |= (1 << sudoku[i][j]);
		col[j] |= (1 << sudoku[i][j]);
		block[i / 3][j / 3] |= (1 << sudoku[i][j]);

		if (sudoku[i][j] == 0) blank.push_back({ i, j });
	}

	recur(0);

	return 0;
}

bit연산으로 구현하면 빨라질까 해서 구현해봤지만.. 아무래도 메모리접근 한번보다는 비트연산의 비용이 더 비싼 것 같다.