[백준-2239] 스도쿠

간단한 백트래킹을 사용한 구현 문제이다.

로직은 생각보다 간단하다. dfs 순회를 하면서 넣으려는 숫자가

• 행에 있는지
• 열에 있는지
• 박스에 있는지

3가지만 확인하면 된다. 이 때 각각을 전부 순회를 때리게 되면 각각 9번의 연산이 생기게 된다. 그렇게 되면 81번의 공간에 9개의 숫자를 확인하되 각각 27번의 check 연산을 하게 되어 복잡도에 큰 문제가 생기지 않는다고 판단된다.

허나 좀더 빠르게 연산하기 위해 해쉬를 두어 숫자를 체크하게 되면 메모리를 조금 더 두어 check 연산을 O(1) 만큼의 복잡도로 처리할 수 있게 된다.

 

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <tuple>
#include <string>
#include <string.h>
#include <stack>
#include <set>
#include <map>


using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
int doqu[10][10];
int row[10][10];
int col[10][10];
int box[3][3][10];
vector<pii> zero;
bool dfs_check = false;

void do_memo(int tx, int ty, int x, int y, int i) {
	row[x][i] = 1;
	col[i][y] = 1;
	box[tx][ty][i] = 1;
	return;
}
void un_memo(int tx, int ty, int x, int y, int i) {
	row[x][i] = 0;
	col[i][y] = 0;
	box[tx][ty][i] = 0;
	return;
}
void print_doqu() {
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			printf("%d", doqu[i][j]);
		}
		printf("\n");
	}
	return;
}
void dfs(int n) {
	if (dfs_check) return;
	if (n == zero.size()) {
		dfs_check = true;
		print_doqu();
		return;
	}
	int cx = zero[n].first;
	int cy = zero[n].second;
	int tp = 0, tx, ty;
	for (int i = 1; i <= 9; i++) {
		if (row[cx][i] == 1) continue;
		if (col[i][cy] == 1) continue;
		tx = (cx - 1) / 3;
		ty = (cy - 1) / 3;
		if (box[tx][ty][i] == 1) continue;

		tp = doqu[cx][cy];
		doqu[cx][cy] = i;
		do_memo(tx, ty, cx, cy, i);
		dfs(n + 1);
		un_memo(tx, ty, cx, cy, i);
		doqu[cx][cy] = tp;
		
	}
	
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int tx, ty;
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			scanf(" %1d", &doqu[i][j]);
			if (doqu[i][j] == 0)
				zero.push_back({ i,j });
			else {
				row[i][doqu[i][j]] = 1;
				col[doqu[i][j]][j] = 1;
				tx = (i - 1) / 3;
				ty = (j - 1) / 3;
				box[tx][ty][doqu[i][j]] = 1;
			}
		}
	}
	dfs(0);

	return 0;
}

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

2239번: 스도쿠