[BOJ] 백준 스도쿠 2239번

백트래킹이 익숙하지 않아서 쉬운 문제랑 내주시는 문제 병행하면서 같이 풀어보고 있는데 아직은 어렵네요. 이번 문제는 다른 사람 풀이를 참고해서 풀었습니다!

풀이 방법

1. row, col, square 변수를 만들어서 각각의 숫자가 행, 열, 사각형에 존재하는지 체크합니다. 예시로 들자면

• 1행에 3이 존재하면 row[1][3] = true, 5열에 1이 존재한다면 col[5][1] = true이 되는 것입니다.
• 사각형도 마찬가지로 9x9 스도쿠를 가로 세로 3등분씩 하여 나눠진 사각형에서 0번째 사각형에 5가 존재한다면 square[0][5] = true가 되는 것입니다.

2. 재귀 종료 조건은 cnt가 81이 되는 것입니다. cnt가 81이 되면 sudoku 전체를 출력하고 프로그램을 종료합니다. 여기서 exit(0) 대신 return을 하게 되면 출력 초과가 나오게 됩니다. 그렇기 때문에 exit(0)으로 프로그램을 완전히 종료해야 합니다. 

3. cnt/9, cnt%9를 하면 각각 x좌표와 y좌표를 구할 수 있습니다. 이번 문제를 풀면서 새로 알게 되었는데 좌표를 이렇게도 나타낼 수 있구나 싶었습니다.

4. 숫자가 이미 채워져 있는 칸은 무시해도 되기 때문에 cnt + 1을 하여 다시 재귀 호출을 하고 0인 칸은 맞는 숫자로 채워주어야 합니다. 이때 숫자가 들어갔다고 해도 그 숫자가 맞다는 보장이 없기 때문에 백트래킹을 사용하여야 합니다.

#include <iostream>
#include <string>

using namespace std;

string sudoku[10];
bool col[10][10], row[10][10], square[10][10];

void solution(int cnt) {
	if (cnt == 81) {
		for (int i = 0; i < 9; i++) {
			cout << sudoku[i] << '\n';
		}
		exit(0);
	}

	int x = cnt / 9; // x좌표
	int y = cnt % 9; // y좌표

	if (sudoku[x][y]=='0') {
		for (int i = 1; i <= 9; i++) {
			if (row[x][i] == false && col[y][i] == false && square[(x / 3) * 3 + (y / 3)][i] == false) {
				row[x][i] = col[y][i] = square[(x / 3) * 3 + (y / 3)][i] = true;
				sudoku[x][y] = i+'0';
				solution(cnt + 1);
				row[x][i] = col[y][i] = square[(x / 3) * 3 + (y / 3)][i] = false;
				sudoku[x][y] = '0';

			}
		}
	}
	else {
		solution(cnt + 1);
	}
}
int main(void) {
	for (int i = 0; i < 9; i++) {
		cin >> sudoku[i];

		for (int j = 0; j < 9; j++) {
			int num = sudoku[i][j] - '0';
			if (num) {
				// 행과 열에 각각 num 숫자가 존재하는지 체크
				// ex. 1행에 num은 존재, 5열에 num은 존재
				col[j][num] = true;
				row[i][num] = true;
				/*
				스도쿠를 9칸으로 나눴을 때 위에서부터
				0 1 2
				3 4 5
				7 8 9
				0에 9가 존재한다면 square[0][9] = true
				*/
				int test = (i / 3) * 3 + j / 3;
				square[test][num] = true;
			}

		}
	}

	solution(0);

}