백준 [2580] 스도쿠

이전 백트래킹 문제들이 일차원 배열을 이용해, 한 줄씩 처리하는 게 가능했다면,

이 문제는 이 방법이 먹히지 않았다.

 

특히, 입력을 2차원 배열의 스도쿠 판만 받아야 한단 생각을 해서 많이 꼬이고 헤맸다.

 

이 문제에서 우리가 고려해야 할 사항은 3가지다.

1. 가로줄

2. 세로줄

3. 3*3 정사각형

 

맨 처음에 스도쿠 판에 저장된 데이터만 가지고 올바른 값이 들어가있는지 검증하는게 무척 어려웠다.

이전에 풀었던 N-Queen 방식대로하면 세로줄까진 어찌어찌 해결해도, 3*3 정사각형에서 매번 헤맸다.

 

해결방법은 생각보다 간단했다.

 

입력을 받고나면,

해당 위치의 가로, 세로 3*3 칸에 입력받은 숫자가 사용됐다는 것만 표시하면 된다.

 

그림으로 설명하자면 이렇게 입력을 받는다면

입력의 일부분

 

가로의 정보를 저장하는 배열엔 이런식으로 저장하고

(코드는 1로 저장했지만, 보기 편하게 숫자 그대로 표시했다.)

x축정보

세로의 정보를 저장하는 배열은

y축 정보

3*3 정사각형 정보를 저장하는 배열은

이런 식으로 스도쿠 판 입력받을 때 같이 저장해준다.

 

이를 이용해 구현한 코드는 다음과 같다.

 

#include <iostream>
#include <stdlib.h>
#include <math.h>
using namespace std;

#define square(i, j) (i / 3) * 3 + (j / 3)

int board[9][9] = { 0, };
int yBoard[9][9] = { 0, };
int xBoard[9][9] = { 0, };
int squareBoard[9][9] = { 0, };

int func(int Count)
{
	int i, j;
	int y = Count / 9, x = Count % 9;
	if (Count == 81)
	{
		for (i = 0; i < 9; i++)
		{
			for (j = 0; j < 9; j++)
				cout << board[i][j] << ' ';
			cout << '\n';
		}
		exit(0);
	}
	if (board[y][x] == 0)
	{
		for (i = 1; i <= 9; i++)
		{
			if (yBoard[y][i] == 0 && xBoard[x][i] == 0 && squareBoard[square(y, x)][i] == 0)
			{
				// 일단 빈 숫자가 있으면 넣어보고,
				board[y][x] = i;
				yBoard[y][i] = 1;
				xBoard[x][i] = 1;
				squareBoard[square(y, x)][i] = 1;
				func(Count + 1);
				// 아니면 다시 뺀다.
				board[y][x] = 0;
				yBoard[y][i] = 0;
				xBoard[x][i] = 0;
				squareBoard[square(y, x)][i] = 0;
			}
		}
	}
	else
		func(Count + 1);
	return 0;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int i, j;
	for (i = 0; i < 9; i++)
	{
		for (j = 0; j < 9; j++)
		{
			cin >> board[i][j];
			if (board[i][j] != 0)
			{
				yBoard[i][board[i][j]] = 1;
				xBoard[j][board[i][j]] = 1;
				squareBoard[square(i, j)][board[i][j]] = 1;
			}
		}
	}
	func(0);
	return 0;
}