간단한 백트래킹을 사용한 구현 문제이다.
로직은 생각보다 간단하다. 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;
}
