스도쿠 (feat. 백준, 2580번)

스도쿠
https://www.acmicpc.net/problem/2580

2580번: 스도쿠

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/2580
#include <iostream>
#include <algorithm>
using namespace std;
int arr[9][9];
bool row[9][10], column[9][10], rect[9][10];
void dfs(register int count) {
	register int x = count / 9;
	register int y = count % 9;
	if (count == 81) {
		for (register int i = 0, j; i < 9; ++i) {
			for (j = 0; j < 9; ++j)
				cout << arr[i][j] << " ";
			cout << "\n";
		}
		exit(0);
	}
	if (!arr[x][y])
		for (register int i = 1; i <= 9; ++i) {
			if (!row[x][i] && !column[y][i] && !rect[(x / 3) * 3 + (y / 3)][i]) {
				row[x][i] = column[y][i] = rect[(x / 3) * 3 + (y / 3)][i] = true;
				arr[x][y] = i;
				dfs(count + 1);
				row[x][i] = column[y][i] = rect[(x / 3) * 3 + (y / 3)][i] = false;
				arr[x][y] = 0;
			}
		}
	else
		dfs(count + 1);
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	for (register int i = 0, j; i < 9; ++i)
		for (j = 0; j < 10; ++j)
			row[i][j] = column[i][j] = rect[i][j] = false;
	for (register int i = 0, j; i < 9; ++i)
		for (j = 0; j < 9; ++j) {
			cin >> arr[i][j];
			if (arr[i][j])
				row[i][arr[i][j]] = column[j][arr[i][j]] = rect[(i / 3) * 3 + (j / 3)][arr[i][j]] = true;
		}
	dfs(0);
	return 0;
}
// *&)*@*

저는 각 행과 각 열, 그리고 각 사각형에 대해서 값을 저장하였습니다.

내용은 아래와 같습니다.

[0][0] ~ [8][8]까지 입력받은 값을 검사하며 0인 경우, row/column/rect에 대해서 1 ~ 9 중 없는 값을 입력하고 다음 인덱스로 넘어가는 방식입니다.

위 그림이 도움이 되셨으면 합니다.