- 문제 링크 : 백준 2580번 - 스도쿠
해결 전략
본 문제는 기초적인 Backtracking(Backtracing) 문제이다. DFS적인 흐름의 탐색 함수를 구성해, 정답이 발견되는 경우, 그 순간 함수의 동작을 멈추고 정답을 출력하면 된다.
본인은 본 문제의 알고리즘을 일찌감치 설계하였지만, 스페셜 저지에서 채점하는 C++ 기준 시간 제한을 충족시키지 못했고, 그것을 충족시키기 위해 함수를 간단화하는 과정이 꽤나 오래 걸렸다. 설계한 알고리즘의 아이디어가 무엇이었으며, 간소화를 어떻게 진행했는지에 대해 서술하겠다.
백트래킹은 사실상 완전 탐색이기 때문에, 우리는 항상 어떻게 Pruning을 할 것인가에 대해 고민해야한다. 본인이 최초에 문제를 접했을 때 발견한 조건은 다음과 같다.
1. board[i][j]를 기준으로, 이 key가 포함된 세로줄엔 1~9가 한번씩만 나타나야 한다.
2. 마찬가지로 i, j 위치가 포함된 가로줄에도 1~9가 한번씩만 나타나야 한다.
3. 마찬가지로 i, j 위치가 포함된 3x3 크기 정사각형에도 1~9가 한번씩만 나타나야 한다.
따라서 우리는, 본 백트래킹 알고리즘의 Pruning 구현을 위의 아이디어를 토대로 어렵지 않게 할 수 있다. 단순한 2차원 배열 서칭에 불과하다.
탈출조건은 어떻게 해주어야 할까. 여러 방법이 있지만, 본인은 최초 보드판 입력 상황 시 0의 개수를 세고, 백트래킹 함수에서 커버한 0의 개수를 세어, 두 cnt값을 대조해 일치하는 경우를 탈출 상황으로 상정하였다.
이 정도 기반 아이디어면 충분히 본 문제에서 요구하는 알고리즘을 설계할 수 있다. 본인이 이때, 시간 초과를 맞이했던 이유는 다음과 같다.
백트래킹 함수에서 board[i][j]가 0인 위치를 찾을 때 중첩 반복문을 사용해 2차원 배열을 순회했다.
이말은 즉슨, 재귀 트리에서 매 함수 호출 시마다 n^2의 반복이 수행되었다는 것이다. 표면적인 예제 출력으로는 별 문제가 없어 보이지만, 문제에서 요구하는 80ms 제한 시간에는 만족하지 못하는 것이다.
이를 처리하는 방법은 무엇일까? 바로 아래와 같다.
DFS 함수의 흐름 자체가 2차원 중첩 반복의 형태로 흐르게 만들면 된다.
이를 위해선 한 가지 센스가 필요하다. 그것은 바로 백트래킹 함수에 정수형 인자 n을 넘겨가는 것이다. 왜냐? n을 9로 나눈 몫과 나머지로 i, j 위치를 설정할 수 있기 때문이다. 이를 통해 ==0일때의 조건을 적절하게 사용하면 백트래킹에 의해 알아서 ==0인 위치에서 분기를 맞이할 수 있다.
한 가지 이때 유의할 점은, 본인의 경우, check라는 함수를 통해 board[i][j] == 0인 위치에 넣을 수 있는 1<=k<=9의 값을 찾고, propercheck라는 함수를 통해 그 k가 들어갔을 때, 스도쿠 규칙이 위반되는지를 확인하였는데,
이때, check 함수는 already라는 전역 배열을 새로 할당하지 않고 계속해서 참조해나간다. 이말은 즉슨, 백트래킹이 이루어지면, already 배열이 훼손되어 있을 가능성이 있다는 것이다. 따라서 already 배열이 백트래킹 상황에서 다시 업데이트될 수 있도록 check 함수를 아래의 코드의 k for문에 넣어주는 것이 중요하다.
백트래킹 시의 기존 데이터 훼손을 주의하라!
아래는 코드이다.
#include <iostream>
// BOJ - 2580 Sudoku
using namespace std;
int board[9][9];
bool already[10];
int proper[10];
int zeros, zerocnt;
void check(int x, int y) {
int xx = (x / 3) * 3, yy = (y / 3) * 3;
for (int i = 0; i < 10; i++) already[i] = false;
for (int i = 0; i < 9; i++) {
already[board[i][y]] = true;
already[board[x][i]] = true;
}
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++)
already[board[xx + i][yy + j]] = true;
}
}
bool propercheck(int x, int y, int k) {
int xx = (x / 3) * 3, yy = (y / 3) * 3;
for (int i = 0; i < 9; i++)
if (board[i][y] == k) return false;
for (int i = 0; i < 9; i++)
if (board[x][i] == k) return false;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++)
if (board[xx + i][yy + j] == k)
return false;
}
return true;
}
bool sudoku(int n) {
if (zerocnt == zeros) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++)
cout << board[i][j] << ' ';
cout << endl;
}
return true;
}
int i = n / 9, j = n % 9;
if (board[i][j] == 0) {
for (int k = 1; k <= 9; k++) {
check(i, j);
if (already[k] == false && propercheck(i, j, k)) {
board[i][j] = k; already[k] = true; zerocnt++;
if (sudoku(n + 1)) return true;
board[i][j] = 0; already[k] = false; zerocnt--;
}
}
}
else return sudoku(n + 1);
return false;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cin >> board[i][j];
if (board[i][j] == 0) zeros++;
}
}
sudoku(0);
return 0;
}
/*
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 2 0 9 0 5 0 0 0
5 9 0 0 3 0 2 0 0
7 0 0 6 0 2 0 0 5
0 0 9 3 5 0 4 6 0
0 5 4 0 0 0 7 8 0
0 8 3 0 2 7 5 0 0
8 0 0 2 0 9 0 0 4
0 0 5 0 4 0 0 2 6
0 0 0 5 0 3 0 7 0
*/