백준 2580: 스도쿠 문제해결 (C++)

 

 

이 문제는 빈칸마다 1-9까지 넣어보되, 불필요하다고 생각되는 숫자는 넣지않는 백트랙킹 방식으로 푸는 문제였다. N-Queen문제와 유사했던 것이다. 2차원 배열의 갯수만큼 재귀를 수행하면서 다음과 같은 방식으로 재귀를 수행한다.

 

• 0을 만난 경우 1-9까지의 수 중에 후보가 될수있는 수들을 하나씩 넣어보고
• 0이 아닌 수를 만난 경우 그냥 재귀를 수행한다.

 

이미 배열에 수가 채워진 경우 가능한 수라는 것이 없다(값이 이미 있으므로). 이때 가능한 수를 찾는 방법은 다음과 같다.

• 가로열에 이미 존재하는 숫자 제외
• 세로열에 이미 존재하는 숫자 제외
• 3*3박스 안에 이미 존재하는 수는 제외

이런 숫자들을 제외하고 남은 숫자들만 하나씩 넣어보는 것이다. 

바닥 조건은 9*9배열을 모두 탐색한 경우로 한다. 즉, 배열의 갯수만큼 재귀를 하는 것이다. 따라서 이때 level은 81까지 존재한다.

즉, 정리를 하면 

• branch: 1-9까지의 수 중 한번도 사용되지 않은 수
• 바닥조건: 81번째로 재귀를 호출한 경우

마지막으로, 사용한 변수들에 대해 말을 하자면, row[9][10]배열은 0-8번째 행에서 숫자가 사용되었는지를 기록해주는 함수이다. row[0][0]의 값이 true이라면 이는 0번째 행에 0이라는 숫자가 존재한다는 뜻이다. 마찬가지로 col[9][10]배열은 각 열에 1-9까지의 수가 존재하는지 기록하는 배열이고, box[9][10]은 해당 3*3박스안에 숫자가 사용되었는지 여부를 기록하는 수이다. 

index를 살펴보면, map[y][x]의 값이 0이어서 해당 행,열,박스를 검사한다고 할때 row[y][1부터9까지],col[y][1부터9까지], row[(y/3)*3+x/3][1부터9까지]를 검사하면 된다. (y/3)*3 + x/3은 박스가 몇번째 박스인지를 구하는 수식이다. (설명생략) 

#include <iostream>

using namespace std;

bool row[9][10] = { false, };
bool col[9][10] = { false, };
bool box[9][10] = { false, };
int map[9][9];

void init() {

	for (int y = 0; y < 9; y++) {
		for (int x = 0; x < 9;x++) {
			scanf("%d",&map[y][x]);
			row[y][map[y][x]] = true;
			col[x][map[y][x]] = true;
			box[(y / 3) * 3 + (x / 3)][map[y][x]] = true;
		}
	}

}

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

void DFS(int level) {
	if (level == 81) {
		out();
		exit(0);
	}
	int y = level / 9;
	int x = level % 9;

	if (map[y][x]) DFS(level + 1);
	else {
		for (int i = 1; i <= 9; i++) {
			if (!row[y][i] && !col[x][i] && !box[(y / 3) * 3 + (x / 3)][i]) {
				map[y][x] = i;
				row[y][i] = true;
				col[x][i] = true;
				box[(y / 3) * 3 + (x / 3)][i] = true;
				DFS(level + 1);
				map[y][x] = 0;
				row[y][i] = false;
				col[x][i] = false;
				box[(y / 3) * 3 + (x / 3)][i] = false;
			}
		}
	}
}

int main() {

	init();

	DFS(0);

	return 0;
}