[Baekjoon] 2580번: 스도쿠

 

 

https://www.acmicpc.net/problem/2580

2580번: 스도쿠

 

빈 칸에 들어갈 숫자를 구하는 과정까지는 빠르게 구현했는데, 백트래킹 알고리즘 구현에서 빈 칸에 들어갈 숫자를 실시간으로 구해서 대입했어야 하는데 그 부분을 실수해서 디버깅에 한참을 소비하고 말았당

 

---

 

문제 해결 과정

착안

빈 칸으로 표시된 칸마다 재귀적으로 현재 칸에 넣을 수 있는 숫자를 넣고, 넣을 수 있는 숫자가 없는 경우에는 이전 단계로 돌아가 다른 숫자를 넣도록 하는 백트래킹 알고리즘을 통해 문제를 해결하고자 하였다. 

 

구현

$i$행 $j$열의 빈 칸을 채울 때, $i$ 번째 행(가로줄)과 $j$ 번째 행(세로줄) 및 $i$행 $j$열을 포함하는 굵은 선으로 구분된 사각형 각각에 대해 1부터 9까지의 숫자가 중복되지 않고 하나씩 나타나야 하므로, 빈 칸에 넣을 수 있는 숫자를 찾는 함수를 아래와 같이 비트마스킹(bitmasking) 기법을 활용하여 구현해보았다.

 

가로줄, 세로줄, 3 $\times$ 3 크기의 사각형에 이미 포함된 숫자들을 비트 표현으로 저장할 int 형의 변수를 mask라고 하고, 숫자 $x \space (1 \le x \le 9)$를 $2^{x-1}$ 자리의 비트와 대응시킨다고 하면, 왼쪽 시프트 연산자(<<)와 비트 OR 연산자(|)를 활용해 아래와 같이 비트마스킹을 할 수 있다.

mask |= 1 << (x - 1);	// x는 가로줄, 세로줄, 3 x 3 사각형에서
			//     빈칸이 아닌 곳에 포함되어 있는 숫자

 

따라서 $i$행 $j$열의 빈 칸과 연관되는 가로줄, 세로줄, 굵은 선으로 구분된 사각형에 포함된 숫자들에 대해 다음과 같이 반복문을 구현하여 mask 변수에 포함 여부를 마스킹 한다.

1. 가로줄, 세로줄 탐색: (가로줄) 행 번호를 $i$로 고정하고 열 번호 $k$에 대해 반복문 실행, (세로줄) 열 번호를 $j$로 고정하고 행 번호 $k$에 대해 반복문을 실행
2. 굵은 선으로 구분된 사각형 탐색: int 형의 나눗셈 특성을 활용해 $i$ / 3 * 3 번째 행부터 $i$ / 3 * 3 + 2 번째 행까지, $j$ / 3 * 3 번째 열부터 $j$ / 3 * 3 + 2 번째 열까지 반복문을 실행

 

가로줄, 세로줄, 굵은 선으로 구분된 사각형 내의 숫자들에 대해 모두 마스킹이 완료되면 mask 변수에 저장된 비트를 반전시킨 다음, 숫자 $m$이 포함되어있는지의 여부를 아래와 같이 확인할 수 있다.

~mask >> (m - 1) & 1;	// 해당 값이 1 (true)이면 숫자 m을 빈칸에 넣을 수 있다
			// 해당 값이 0 (false)이면 숫자 m은
                        //     가로줄, 세로줄 또는 3 x 3 사각형 내에 이미 포함된 경우이다

 

위와 같이 함수를 구현해 활용하면 백트래킹(backtracking) 알고리즘에 기반해 모든 빈칸에 대해 순차적으로 숫자를 넣어본 다음, 넣을 수 있는 숫자가 없으면 이전 과정으로 되돌아가는 방법으로 문제를 해결할 수 있다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <vector>

using namespace std;

struct Coord
{
	int Row;
	int Col;
};

int Sudoku[9][9];
vector<Coord> Blanks;
int Filled;

bool IsFillable(Coord coord, int n)
{
	int row = coord.Row, col = coord.Col;
	int mask = 0;

	for (int i = 0; i < 9; i++)
	{
		if (Sudoku[row][i])
			mask |= 1 << (Sudoku[row][i] - 1);

		if (Sudoku[i][col])
			mask |= 1 << (Sudoku[i][col] - 1);
	}

	int rStart = row / 3 * 3;
	int cStart = col / 3 * 3;
	for (int i = rStart; i < rStart + 3; i++)
		for (int j = cStart; j < cStart + 3; j++)
			if (Sudoku[i][j])
				mask |= 1 << (Sudoku[i][j] - 1);

	return ~mask >> (n - 1) & 1;
}

void FillBlanks()
{
	Coord blank = Blanks[Filled];
	for (int i = 1; i <= 9; i++)
	{
		// fill the blank if i is a fillable number
		if (IsFillable(blank, i))
		{
			Sudoku[blank.Row][blank.Col] = i;
			Filled++;
			if (Filled < Blanks.size())
				FillBlanks();	// recursion
		}
	}

	// backtrack to blank
	if (Filled != Blanks.size())
	{
		Sudoku[blank.Row][blank.Col] = 0;
		Filled--;
	}
}

int main()
{
	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++)
		{
			cin >> Sudoku[i][j];
			if (!Sudoku[i][j])
				Blanks.push_back(Coord{ i, j });
		}

	if (!Blanks.empty())
		FillBlanks();

	// print
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
			cout << Sudoku[i][j] << " ";
		cout << "\n";
	}

	return 0;
}

 

실행 결과