백준/2580번/스도쿠/골드4

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

문제 설명

Site: Baekjoon
Number: 2580
Category: 백트래킹
Rank: Gold 4

주어진 스도쿠를 해결하는 문제이다.

스도쿠의 해결법이 여러가지인 경우 그 중 하나를 출력하면 된다.

백트래킹 문제이며, dfs를 통해 풀었다. 스도쿠 배열을 입력받을 때 비어있는 좌표들을 dq에 받아 dq가 빌때까지 dfs를 진행하였다.

dfs가 빈 경우 해답을 찾은 것이므로 답을 출력하고 추가적인 연산을 통해 시간이 늘어나는 것을 방지하기 위해 exit(0)으로 코드를 종료하였다.

#include <iostream>
#include <deque>

#define PII pair<int, int>

using namespace std;

int sudoku[9][9];

// 해당 좌표에 num이 들어갈 수 있는지 판별
bool Check(int x, int y, int num)
{
	for(int i = 0; i < 9; i++)
	{
		if (sudoku[x][i] == num || sudoku[i][y] == num)
			return false;
	}

	int a = (x / 3) * 3;
	int b = (y / 3) * 3;

	for(int i = a; i < a + 3; i++)
	{
		for(int j = b; j < b + 3; j++)
		{
			if (sudoku[i][j] == num)
				return false;
		}
	}

	return true;
}

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

void dfs(deque<PII>& dq)
{
	if(dq.empty())
	{
		Print();
		exit(0);
	}

	PII cur = dq.front();
	dq.pop_front();

	for(int i = 1; i < 10; i++)
	{
		if(Check(cur.first, cur.second, i))
		{
			sudoku[cur.first][cur.second] = i;
			dfs(dq);
			sudoku[cur.first][cur.second] = 0;
		}
	}

	dq.emplace_front(cur);
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int cnt = 0;

	deque<pair<int, int>> dq;

	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cin >> sudoku[i][j];
			if(sudoku[i][j] == 0)
			{
				dq.emplace_back(i, j);
				cnt++;
			}
		}
	}

	dfs(dq);

	return 0;
}