[백준] 2580 - 스도쿠

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

2580번: 스도쿠

• 재귀를 이용한 백트래킹을 사용해야 풀 수 있는 문제다.
• 나는 문제를 풀었지만 452ms 가 나왔고 채점 현황에서 다른 사람들과 비교했을 때 매우 느린 수준이다.
• 따라서 다시 문제를 분석하여 코드를 개선할 필요가 있다.
• 나는 0이 나오는 위치를 pair<>로 저장하여 사용했다.
• 가장 예제로 좋은 것은 9 x 9 의 칸이 모두 '0' 일 경우 일까?

---

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

vector<vector<int>> inputList;

typedef pair<int, int> ZERO_POS;
deque<ZERO_POS> zeroPosList;

// debug
#define debug_m 0

// method
void Print();
void Sudoku(int x, int y);
bool CheckV(int x, int y, int value);
bool CheckH(int x, int y, int value);
bool CheckNemo(int x, int y, int value);

int main()
{
	// init
	std::ios::sync_with_stdio(false);
	
	// input
	for (int x = 0; x < 9; x++)
	{
		vector<int> tempList;
		for (int y = 0; y < 9; y++)
		{
			int input = 0;
			(void)scanf("%d", &input);

			if (0 == input)
			{
				ZERO_POS zeroPos(x, y);
				zeroPosList.push_back(zeroPos);
			}

			tempList.push_back(input);
		}
		inputList.push_back(tempList);
	}

	// Calc
	ZERO_POS startPos = zeroPosList.front();
	zeroPosList.pop_front();
	Sudoku(startPos.first, startPos.second);

	// print
	Print();

	return 0;
}

void Print()
{
#if debug_m
	printf("\n");
#endif

	// Print
	for (auto x : inputList)
	{
		for (auto y : x)
			printf("%d ", y);
		printf("\n");
	}

}

void Sudoku(int x, int y)
{
	for (int value = 1; value <= 9; value++)
	{
		const bool isOkH = CheckH(x, y, value);
		if (false == isOkH)
			continue;

		const bool isOkV = CheckV(x, y, value);
		if (false == isOkV)
			continue;

		const bool isOkNemo = CheckNemo(x, y, value);
		if (false == isOkNemo)
			continue;
		else
		{
			inputList[x][y] = value;

#if debug_m
			Print();
#endif

			// stop
			if (true == zeroPosList.empty())
				return;

			// next
			ZERO_POS nextZeroPos = zeroPosList.front();
			zeroPosList.pop_front();

			Sudoku(nextZeroPos.first, nextZeroPos.second);

			// stop
			if (true == zeroPosList.empty())
				return;

			zeroPosList.push_front(nextZeroPos);
			inputList[x][y] = 0;
		}		
	}
}

bool CheckV(int x, int y, int value)
{
	bool numCheck[10] = { false, };

	for (int idx = 0; idx < 9; idx++)
	{
		if (x == idx)
			continue;
		
		const int arrVal = inputList[idx][y];
		if (false == numCheck[arrVal])
		{
			numCheck[arrVal] = true;
		}
	}

	if (true == numCheck[value])
		return false;

	return true;
}

bool CheckH(int x, int y, int value)
{
	bool numCheck[10] = { false, };

	for (int idx = 0; idx < 9; idx++)
	{
		if (y == idx)
			continue;

		const int arrVal = inputList[x][idx];
		if (false == numCheck[arrVal])
		{
			numCheck[arrVal] = true;
		}
	}

	if (true == numCheck[value])
		return false;

	return true;
}

bool CheckNemo(int x, int y, int value)
{
	bool numCheck[10] = { false , };

	int nemoX = 0;
	int nemoY = 0;

	if (0 <= x && 2 >= x)
		nemoX = 0;
	else if (3 <= x && 5 >= x)
		nemoX = 3;
	else
		nemoX = 6;

	if (0 <= y && 2 >= y)
		nemoY = 0;
	else if (3 <= y && 5 >= y)
		nemoY = 3;
	else
		nemoY = 6;

	for (int startX = nemoX; startX < nemoX + 3; startX++)
	{
		for (int startY = nemoY; startY < nemoY + 3; startY++)
		{
			if (x == startX && y == startY)
				continue;

			const int arrVal = inputList[startX][startY];
			if (false == numCheck[arrVal])
				numCheck[arrVal] = true;
		}
	}

	if (true == numCheck[value])
		return false;

	return true;
}