[알고리즘/문제풀이/BOJ 2580번] 스도쿠

이번 문제는 스도쿠를 푸는 문제입니다. 스도쿠의 규칙에 위배되지 않도록 빈칸을 적절하게 채움으로써 간단하게 문제를 해결할 수 있었습니다.

스도쿠의 빈칸을 채우기 위해 모든 경우를 탐색하는 백트래킹 기법을 사용하였습니다. 빈 칸의 좌표를 저장한 후 빈 칸의 개수만큼의 높이를 가진 트리를 탐색하는 재귀함수를 통해 백트래킹을 구현하였습니다. 재귀함수를 한번씩 통과할 때마다 빈 칸이 한 개씩 채워지며 모든 빈 칸이 채워지면 스도쿠를 출력하도록 하였습니다. 

문제에서 제약조건으로 c언어의 경우 80ms 내에 처리하도록 하였으며, 작성한 코드는 76ms에 스도쿠를 처리할 수 있었습니다. 백트래킹을 빠르게 실행하기 위해서는 필요없는 경우를 무시하는 가지치기가 필요합니다.

재귀 함수에서 스도쿠를 출력하자 마자 프로그램이 종료될 수 있도록 stdlib.h에 함수 원형이 있는 exit(0) 함수를 사용하였습니다. 파라미터로 주어진 0은 프로그램이 어떠한 에러없이 정상적으로 종료됨을 의미합니다.

작성한 코드는 다음과 같습니다.

#include<stdio.h>
#include<stdlib.h>

int sudoku[10][10];
int blank[100][2];

int cnt = 0;
int end = 0;

void final_process() {
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			printf("%d ", sudoku[i][j]);
		}
		printf("\n");
	}
}

void sudoku_solver(int depth) {
	int check[10] = { 0,0,0,0,0,0,0,0,0,0 };

	if (depth == cnt) {
		final_process();
		exit(0);
	}
	else {
		for (int i = 1; i <= 9; i++) {
			check[sudoku[blank[depth][0]][i]] = 1;
			check[sudoku[i][blank[depth][1]]] = 1;
		}

		for (int i = 1; i <= 3; i++)
			for (int j = 1; j <= 3; j++)
				check[sudoku[(blank[depth][0] - 1) / 3 * 3 + j][(blank[depth][1] - 1) / 3 * 3 + i]] = 1;

		for (int i = 1; i <= 9; i++) {
			if (check[i] == 1) 
				continue;

			sudoku[blank[depth][0]][blank[depth][1]] = i;
			sudoku_solver(depth + 1);
			sudoku[blank[depth][0]][blank[depth][1]] = 0;
		}
	}

	return;
}

int main(void) {
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			scanf("%d", &sudoku[i][j]);
			if (sudoku[i][j] == 0) {
				blank[cnt][0] = i;
				blank[cnt][1] = j;
				cnt++;
			}
		}
	}

	sudoku_solver(0); //0개의 빈칸에 숫자가 빠짐없이 채워졌을 때 가능한 스도쿠의 출력 중 1개를 출력하는 함수
}

문제의 지문에 대해서는 저작권으로 인해 링크를 첨부하였습니다.

2580번: 스도쿠 (acmicpc.net)