[백준] 스도쿠

유의할점

끝을 만나면 종료시킨다.
종료가 안됬다는것은 현재 해가 답이 아니라는것이다. 내가 넣는 모든 숫자가 답이 아닐수있다 이때는 뒤로 돌아가야한다.(Backtracking) 뒤로 돌아갈때 0을 수정한 흔적을 지워야한다. 그 접근 자체가 잘못 됬을 수 있기 때문이다. 백트래킹에 있어서 원래의 함수로 돌아간다라는 의미를 잘생각하자.

풀이

해당 함수는 (x , y) 부터 시작해서 스도쿠를 완성시키는 함수이다.

범위는 (0 , 0)에서 (8 , 8)까지 존재한다.

y가 9일경우 스도쿠가 완성된것이다. 출력하고 프로그램을 강제 종료시킨다.

arr[y][x]이 0이 아닌 경우.

dfs(y , x + 1)을 호출한다. 이를 위해서 전처리가 필요 x가 9일경우 y++; x=0;

arr[y][x]가 0인경우

가능한 숫자를 검사하고 (가로/세로/사각형) 해당 숫자로 검사한다. 해당 지점에서 모든 경우를 시도했어도, 해당 지점 부모(이전에 호출한 함수)가 해가 아닌 경우 해당 모든 경우가 틀렸을수있다.

모두 시도했음에도 프로그램이 종료되지 않았다는것은 부모가 틀렸다는 것이다. 틀린값은 지워놓고 가야한다. 마지막에 arr[y][x] = 0을 호출한다.

코드

C++

#include <iostream>
using namespace std;

int arr[9][9];

void printRes() {
	for (int y = 0; y < 9; y++) {
		for (int x = 0; x < 9; x++) {
			printf("%d ", arr[y][x]);
		}
		printf("\n");
	}

}

void checkArea(const int &y, const int &x, bool* numberCheck) {
	int dy = (y / 3) * 3;
	int dx = (x / 3) * 3;
	
	for (int y = 0; y < 3; y++)
		for (int x = 0; x < 3; x++)
			numberCheck[arr[y + dy][x + dx]] = true;
	return;
}

void checkRow(const int &y, bool *numberCheck) {
	for (int i = 0; i < 9; i++)
		numberCheck[arr[y][i]] = true;
	return;
}

void checkCol(const int &x, bool* numberCheck) {
	for (int i = 0; i < 9; i++)
		numberCheck[arr[i][x]] = true;
	return;
}

//y , x 부터 시작해서 스도쿠를 완성한다.
void dfs(int y, int x) {
	if (x == 9) {
		y++;
		x = 0;
	}

	if (y == 9) {
		printRes();
		exit(0);
		return;
	}

	if (arr[y][x])
		return dfs(y, x + 1);
		
	bool numberCheck[10]; // 1부터 9까지 있으면 true
	fill_n(numberCheck, 10, false);
	//가로 검사
	checkRow(y, numberCheck);
	//세로 검사
	checkCol(x, numberCheck);
	//네모칸 검사
	checkArea(y, x, numberCheck);

	for (int i = 1; i < 10; i++) {
		if (!numberCheck[i]) {
			arr[y][x] = i;
			dfs(y, x + 1);
		}
	}
	arr[y][x] = 0;
	return;
}

int main() {
	for (int y = 0; y < 9; y++)
		for (int x = 0; x < 9; x++)
			scanf(" %d", &arr[y][x]);
	dfs(0, 0);
}