[백준 C++] 2239 스도쿠 - 백트래킹

2239번: 스도쿠

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

const int MaxSize = 9;

bool bFound;
int Solution[MaxSize][MaxSize];

int Board[MaxSize][MaxSize];
bool CheckRow[MaxSize][MaxSize + 1];
bool CheckCol[MaxSize][MaxSize + 1];
bool CheckArea[MaxSize][MaxSize + 1];

void Init()
{
	for (int i = 0; i < MaxSize; ++i)
	{
		string Line;
		cin >> Line;
		for (int j = 0; j < MaxSize; ++j)
		{
			int Num = Line[j] - '0';
			Board[i][j] = Num;
			CheckRow[i][Num] = true;
			CheckCol[j][Num] = true;
			CheckArea[(i / 3) * 3 + (j / 3)][Num] = true;
		}
	}
}

void Print()
{
	for (int i = 0; i < MaxSize; ++i)
	{
		for (int j = 0; j < MaxSize; ++j)
		{
			cout << Solution[i][j];
		}
		cout << '\n';
	}
}

void DFS(int Count)
{
	int Row = Count / MaxSize;
	int Col = Count % MaxSize;

	if (bFound || Count == 81)
	{
		bFound = true;
		memcpy(Solution, Board, sizeof(Solution));
		return;
	}

	if (Board[Row][Col] == 0)
	{
		for (int Num = 1; Num <= MaxSize; ++Num)
		{
			if (CheckRow[Row][Num] == false
				&& CheckCol[Col][Num] == false
				&& CheckArea[(Row / 3) * 3 + (Col / 3)][Num] == false)
			{
				Board[Row][Col] = Num;
				CheckRow[Row][Num] = true;
				CheckCol[Col][Num] = true;
				CheckArea[(Row / 3) * 3 + (Col / 3)][Num] = true;
				DFS(Count + 1);

				if (bFound)
				{
					return;
				}

				Board[Row][Col] = 0;
				CheckRow[Row][Num] = false;
				CheckCol[Col][Num] = false;
				CheckArea[(Row / 3) * 3 + (Col / 3)][Num] = false;
			}
		}
	}
	else
	{
		DFS(Count + 1);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	Init();
	DFS(0);
	Print();
}

---

 

답이 여러 개 있을 때 사전식으로 앞서는 것을 출력해야 하기 때문에

깊이 우선 탐색 기법을 이용해서 푸는 문제입니다. (+ 백트래킹)

 

풀이 과정은 Count를 0부터 1씩 늘려가며 행, 열 번호를 지정해주면서 깊이 우선 탐색을 수행하도록 했습니다.

해당 칸에 1부터 9까지 넣어보면서 같은 행, 열, 영역에 같은 숫자가 존재하는지 체크하고

존재하지 않다면 해당 숫자를 해당 칸에 넣고 다음 Count로 넘어가도록 했습니다.