백준 2239 (스도쿠) c++

문제

2239번: 스도쿠

주어진 스도쿠를 완성시키는 문제입니다.

 

들어갈 수 의 가로와 세로 그리고 포함된 미니 박스에 중복된 수가 없어야 합니다.

이를 위해서 boolean 형으로 체크할 필요가 있습니다.

그래서 총 3개의 불린형 2차원 배열을 설정해줍니다.

미니 박스

ex) garo[5][8] = true : 가로 5번째 줄에 8이 존재

     sero[5][8] = false : 세로 5번째 줄에 8이 존재하지 않음

     box[5][8] = false : 5번째 미니 박스에 8이 존재하지 않음

string str[10];
int arr[10][10];
bool garo[10][10];
bool sero[10][10];
bool box[10][10];
void sdouq(int cnt);
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	for (int i = 0; i < 9; i++)
		cin >> str[i];
	
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			arr[i][j] = str[i][j] - '0';
			if (arr[i][j]) {
				garo[i][arr[i][j]] = true;
				sero[j][arr[i][j]] = true;
				box[(i / 3) * 3 + (j / 3)][arr[i][j]] = true;
			}
		}
	}

따라서 이렇게 입력을 받아 줍니다.

garo[i][arr[i][j]] = ture : i번째 가로 줄에 arr[i][j] 숫자가 존재

sero[j][arr[i][j]] = ture : j번째 세로 줄에 arr[i][j] 숫자가 존재

box[(i / 3) * 3 + (j / 3)][arr[i][j]] = true : (i / 3) * 3 + (j / 3)번째 미니박스에 arr[i][j] 숫자가 존재

(i / 3) * 3 + (j / 3) 은 미니박스의 위치를 가리킵니다.

ex) (5, 8) 은 5번째 박스에 존재합니다 = (5 / 3) * 3 + (8 / 3) = 1 * 3 + 2 = 5

void sdouq(int cnt) {
	if (cnt == 81) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << arr[i][j];
			}
			cout << '\n';
		}
		exit(0);
	}
	int x = cnt / 9;
	int y = cnt % 9;
	
	if (!arr[x][y]) {
		for (int i = 1; i <= 9; i++) {
			if (garo[x][i] == false && sero[y][i] == false && box[(x / 3) * 3 + (y / 3)][i] == false) {
				garo[x][i] = true;
				sero[y][i] = true;
				box[(x / 3) * 3 + (y / 3)][i] = true;
				arr[x][y] = i;
				sdouq(cnt + 1);
				arr[x][y] = 0;
				garo[x][i] = false;
				sero[y][i] = false;
				box[(x / 3) * 3 + (y / 3)][i] = false;
			}
		}
	}
	else sdouq(cnt + 1);
}

cnt는 0부터 81까지 계속 재귀적으로 진행합니다.

cnt =81 이면 완성된 스도쿠를 출력하고 종료합니다.

x(가로)와 y(세로)를 설정해줍니다.

arr[x][y] 

x = cnt / 9

y = cnt % 9  가 됩니다.

 

이제 arr[x][y]가 0이면 숫자를 넣어줘야 하므로 1부터 9까지 반복문을 돌면서 가능한 숫자를 추출해 냅니다.

여기서 가능한 숫자가 있다고 확정하면 안되는게 모든 수들이 서로 가로, 세로 , 미니박스에 영향을 주므로 

확정된 숫자가 틀릴 수 도 있습니다. 

따라서 sdouq함수를 탈출할 시에는 다시 원상태로 되돌려줘야 합니다.

arr[x][y]= 0 

garo[x][i] =false 등등

---

전체 코드 입니다

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
string str[10];
int arr[10][10];
bool garo[10][10];
bool sero[10][10];
bool box[10][10];
void sdouq(int cnt);
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	for (int i = 0; i < 9; i++)
		cin >> str[i];
	
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			arr[i][j] = str[i][j] - '0';
			if (arr[i][j]) {
				garo[i][arr[i][j]] = true;
				sero[j][arr[i][j]] = true;
				box[(i / 3) * 3 + (j / 3)][arr[i][j]] = true;
			}
		}
	}

	
	sdouq(0);


	return 0;
}
void sdouq(int cnt) {
	if (cnt == 81) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << arr[i][j];
			}
			cout << '\n';
		}
		exit(0);
	}
	int x = cnt / 9;
	int y = cnt % 9;
	
	if (!arr[x][y]) {
		for (int i = 1; i <= 9; i++) {
			if (garo[x][i] == false && sero[y][i] == false && box[(x / 3) * 3 + (y / 3)][i] == false) {
				garo[x][i] = true;
				sero[y][i] = true;
				box[(x / 3) * 3 + (y / 3)][i] = true;
				arr[x][y] = i;
				sdouq(cnt + 1);
				arr[x][y] = 0;
				garo[x][i] = false;
				sero[y][i] = false;
				box[(x / 3) * 3 + (y / 3)][i] = false;
			}
		}
	}
	else sdouq(cnt + 1);
}