[백준2239] 스도쿠 (C++)

📌 문제

BOJ 바로가기

스도쿠 판을 채우는 백트래킹 문제이다.
2580번 문제와 유사하다.

🔎 풀이

📍 bool형 배열 세 개를 만드는 것이 중요하다.

row[A][B] = true는 A번째 행에 B라는 숫자가 존재함을 뜻한다.
col[A][B] = true는 A번째 열에 B라는 숫자가 존재함을 뜻한다.
square[A][B] = true는 A번째 사각형에 B라는 숫자가 존재함을 뜻한다.

기본 세팅은 다음과 같다.

bool row[10][10] = { false, };
bool col[10][10] = { false, };
bool square[10][10] = { false, };

📍 숫자를 입력받는 동시에 bool형 배열 세 개를 채워준다.

📍 빈칸이 비어있다면 1부터 9까지의 숫자를 넣어주고 앞선 bool형 배열 세 개의 값을 true로 바꿔준 후, 재귀함수를 돌린다.

🚩 소스코드

if (row[x][i] == false && col[y][i] == false && square[square_num][i] == false) {
	map[x][y] = i;
	row[x][i] = true;
	col[y][i] = true;
	square[square_num][i] = true;
	go(idx + 1);

📍 숫자를 넣었는데 틀린 값일 경우에는 bool형 배열 세 개의 값을 다시 false로 바꿔주어야 한다! (백트래킹)

map[x][y] = 0;
row[x][i] = false;
col[y][i] = false;
square[square_num][i] = false;

😨 몇 번째 사각형인지 구하는 과정이 조금 까다로웠다.

x와 y의 인덱스가 1번부터 시작하고 사각형의 번호를 1번부터 9번까지 부여할 경우, 사각형의 번호는 다음과 같이 나타낼 수 있다.
int square_num = (x - 1) / 3 * 3 + (y - 1) / 3 + 1;

x와 y의 인덱스가 0번부터 시작하고 사각형의 번호를 0번부터 부여할 경우, 사각형의 번호는 다음과 같다.
int square_num = x / 3 * 3 + y / 3;

나는 전자를 택했는데, 후자가 비교적 깔끔한 것 같다.

#include <iostream>
using namespace std;

int map[10][10];
// arr[A][B]는 A번째 행에 B라는 숫자가 존재한다는 의미
bool row[10][10] = { false, };
bool col[10][10] = { false, };
bool square[10][10] = { false, };

void print() {
	for(int i = 1; i <= 9; i++) {
		for(int j = 1; j <= 9; j++)
			cout << map[i][j];
		cout << '\n';
	}
}

void go(int idx) {
	if (idx > 81) {
		print();
		exit(0);
	}
	int x = (idx - 1) / 9 + 1;
	int y = (idx - 1) % 9 + 1;
	int square_num = (x - 1) / 3 * 3 + (y - 1) / 3 + 1;
	if (map[x][y] == 0) {
		for(int i = 1; i <= 9; i++) {
			if (row[x][i] == false && col[y][i] == false && square[square_num][i] == false) {
				map[x][y] = i;
				row[x][i] = true;
				col[y][i] = true;
				square[square_num][i] = true;
				go(idx + 1);
				map[x][y] = 0;
				row[x][i] = false;
				col[y][i] = false;
				square[square_num][i] = false;
			}
		}
	}
	else
		go(idx + 1);
}

int main() {
	for(int i = 1; i <= 9; i++) {
		for(int j = 1; j <= 9; j++) {
			scanf("%1d", &map[i][j]);
			row[i][map[i][j]] = true;
			col[j][map[i][j]] = true;
			square[((i - 1) / 3) * 3 + (j - 1) / 3 + 1][map[i][j]] = true;
		}
	}
	go(1);
	return 0;
}