문제
문제접근
문제 이해
- 스도쿠는 9×9 배열, 즉 81칸으로 이뤄져있습니다.
- 0번째 칸부터 재귀를 돌면서
0
이 들어있는 칸에 대해서는 임의의 숫자를 넣습니다.
- 숫자를 넣을 때는 가로와 세로 그리고 포함된 그룹을 검사해서 적합한 숫자를 찾습니다.
- 1~9 까지 수는 각 행과 열 그리고 그룹에 단 하나만 존재해야 합니다.
- 저는 코드상에서 매 재귀마다 가로, 세로 그리고 그룹을 검사하는 방법을 사용했습니다.
- 이 방법은 후술할 방법보다 더 오랜 시간이 걸리는 방법입니다.
- 그나마 조금 더 효율적으로 하기 위해, 저는 스도쿠를 입력받을 때
0
의 자리를 따로 저장해서 재귀 호출 횟수를 줄이는 방법을 사용했습니다.
- 혹은 전역변수에
bool
타입 배열 3개를 만들어서 검사하는 방법도 있습니다.
row[i][num]
: i
번째 행에 num
이라는 수가 있다면 true
.
col[i][num]
: i
번째 열에 num
이라는 수가 있다면 true
.
group[i][num]
: i
번째 그룹에 num
이라는 수가 있다면 true
.
(y, x)
라는 좌표는 (y / 3) * 3 + x / 3
번째 그룹에 속해있습니다.
그 그룹의 시작점 좌표는 ((y / 3) * 3), (x / 3 ) * 3)
입니다.
코드
#include <iostream>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
struct Pos { int y, x; };
int emptyCnt, map[9][9];
Pos empty[81];
void go(int cnt) {
if (cnt == emptyCnt) {
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j)
cout << map[i][j] << ' ';
cout << '\n';
}
exit(0);
}
bool table[10] = {false, };
int cy = empty[cnt].y, cx = empty[cnt].x;
int gy = (cy / 3) * 3, gx = (cx / 3) * 3;
for (int i = 0; i < 9; ++i) {
if (!table[map[cy][i]]) table[map[cy][i]] = true;
if (!table[map[i][cx]]) table[map[i][cx]] = true;
}
for (int i = gy; i < gy + 3; ++i)
for (int j = gx; j < gx + 3; ++j)
if (!table[map[i][j]]) table[map[i][j]] = true;
for (int i = 1; i <= 9; ++i) {
if (table[i]) continue;
map[cy][cx] = i;
go(cnt + 1);
map[cy][cx] = 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 >> map[i][j];
if (map[i][j] == 0) empty[emptyCnt++] = {i, j};
}
go(0);
}
재풀이 코드
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
int map[9][9];
bool row[9][10], col[9][10], group[9][10];
vector<pair<int, int>> emptySpace;
int getGroupNum(int y, int x) {
return (y / 3) * 3 + (x / 3);
}
void solve(int cnt) {
if (cnt == emptySpace.size()) {
for (int y = 0; y < 9; ++y) {
for (int x = 0; x < 9; ++x)
cout << map[y][x] << ' ';
cout << '\n';
}
exit(0);
}
for (int i = 1; i <= 9; ++i) {
int y = emptySpace[cnt].first, x = emptySpace[cnt].second;
if (row[y][i] || col[x][i] || group[getGroupNum(y, x)][i]) continue;
map[y][x] = i;
row[y][i] = col[x][i] = group[getGroupNum(y, x)][i] = true;
solve(cnt + 1);
row[y][i] = col[x][i] = group[getGroupNum(y, x)][i] = false;
map[y][x] = 0;
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(NULL);
for (int y = 0; y < 9; ++y)
for (int x = 0; x < 9; ++x) {
cin >> map[y][x];
row[y][map[y][x]] = col[x][map[y][x]] = group[getGroupNum(y, x)][map[y][x]] = true;
if (map[y][x] == 0) emptySpace.push_back({y, x});
}
solve(0);
}
결과
재풀이 결과