Boj 2580 스도쿠

1. 문제

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

2580번: 스도쿠

2. 문제의 요구

빈칸을 채워 스도쿠를 완성하라!

 

3. 적용할 알고리즘

백트래킹이 가능하다.

처음에는 빈칸이 10개인 경우 9의 10승으로 시간초과가 날 거라 예상했지만

빈칸을 채울 때마다 조건 확인을 해주면 그 다음 재귀로 넘어가는 경우의 수는 많이 줄어든다.

 

4. 설명

빈칸에 1~9까지 수를 대입해보고

스도쿠 조건에 만족하지 않는다면 그 경우는 패스하고,

만족한다면 다음 빈칸으로 넘어간다.

만약 만족하는 수가 없다면 이전 선택이 잘못된 것이므로

이전의 빈칸으로 돌아간다.

빈칸이 모두 채워졌다면 종료한다.

 

5. 코드

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<tuple>

using namespace std;

const int INF = 0x7f7f7f7f;

typedef long long ll;

int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

int board[10][10];

vector<pair<int,int>> zero;

bool Check(int x, int y, int num)
{
	for (int i = 0; i < 9; i++)
	{
		if (board[i][y] == num) return false;
		if (board[x][i] == num) return false;
	}

//주변 9개 칸 중 같은 것이 있는지 확인
//*주의* C언어에서 x / 3 * 3 != x 이다. 
// '/'연산은 나머지를 날려버리기 때문이다.
	for (int i = x / 3 * 3; i < x / 3 * 3 + 3; i++)
	{
		for (int j = y / 3 * 3; j < y / 3 * 3 + 3; j++)
		{
			if (board[i][j] == num) return false;
		}
	}

	return true;
}

int ans[10][10];

void solve(int cur)
{
//빈 칸을 다 채웠을 시 종료
	if (cur == zero.size())
	{
		for (int i = 0; i < 9; i++)
			for (int j = 0; j < 9; j++) ans[i][j] = board[i][j];
		return;
	}

	int cx, cy;
	tie(cx, cy) = zero[cur];

//적절한 수인지 확인 후 다음 빈칸으로 넘어간다
	for (int i = 1; i <= 9; i++)
	{
		if (Check(cx, cy, i))
		{
			board[cx][cy] = i;
			solve(cur + 1);
			board[cx][cy] = 0;
		}
	}
}

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

	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cin >> board[i][j];
			if (board[i][j] == 0) zero.push_back({ i, j });
		}
	}

	solve(0);

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

6. 느낀 점

그냥 대충 순열, 조합 등으로 계산하고 백트래킹 불가로 생각하지 말고

어떠한 조치를 취하면 백트래킹의 시간복잡도가 대폭 줄어들어

완전탐색이 가능하다는 걸 기억하자