문제 이해 단계
문제는 우리가 익히 아는 스도쿠 규칙과 다를 것이 없다.
9x9 스도쿠가 주어지고 빈칸은 0으로 주어진다.
이러한 입력이 주어졌을 때 빈칸을 채워 스도쿠를 완성시키는 문제이다.
여기서 스도쿠를 완성시킬 수 없는 경우는 존재하지 않는다.
문제 접근 단계
해당 문제에서의 특징은 맵(스도쿠)의 크기가 9x9로 고정되어 있다는 것이다.
그렇기 때문에 완전탐색, 백트래킹 등 다양한 탐색이 가능하다.
그래도 시간제한이 주어졌기 때문에 조건을 둬서 쓸데없는 탐색을 줄이는 편이 나아 보인다.
다른 건 다 제쳐두고 맵의 칸 하나의 관점으로 바라보자.
해당 자리가 비어있어서 숫자 1~9까지 하나를 넣어야 한다.
어떤 절차를 걸쳐서 넣을까?
스도쿠의 규칙에 따라 아래 세 곳에 똑같은 숫자가 있다면, 그 수는 제외하는 방식으로 할 것이다.
map [i][j] = i행 j열에 들어갈 수 있는 수
1. i 행에 있는 모든 수
2. j열에 있는 모든 수
3. (i, j)가 속해있는 사각형 그룹에 속해있는 모든 수
그렇기 때문에 한 칸의 들어갈 수를 알기 위해서는
위 3가지의 정보를 검사해줘야 한다.
다음으로 문제가 되는 부분은, 들어갈 수 있는 숫자가 다양한데 그 숫자를 넣는 게 맞을까?
어떤 수가 맞는지 확인해 보려면 그 수를 넣어보고 다른 수들을 끝까지 채워보는 수밖에 없다.
그렇게 진행하다가 빈칸을 채울 수 없는 경우가 생기면,
그 수를 넣는 것이 틀렸다는 것을 알 수 있을 것이다.
위에서 알 수 있는 점은 해당 값이 맞는지 확인하기 위해
들어갈 수 있는 값을 하나씩 넣어서 끝까지 진행하여 확인해 보는 수밖에 없다.
결국 빈칸에 넣을 수 있는 가능한 경우 수 조합 중,
9x9 스도쿠를 끝까지 탐색했을 때 빈칸이 하나도 남지 않는 것이 정답이 되는 것이다.
결국 수를 넣는 것을 반복하면서 결과를 확인하고 틀렸다면, 다시 돌아가서 다시 다른 수를 넣어보는 것이다.
위 생각이 백트래킹의 개념과 비슷하다는 생각이 들어서 백트래킹으로 접근하였다.
백트래킹 방식
백트래킹은 재귀함수를 통해 구현하는 것이 편리하기 때문에 재귀함수를 사용하였다.
그리고 어차피 빈칸을 채울 숫자만 찾는 것이기 때문에 전체 맵에 대해서 백트래킹을 하는 것보다
빈칸의 위치정보를 담은 배열을 구성하고, 그 배열을 통해 백트래킹을 하기로 했다.
방식은 아래와 같다.
탐색은 순차적으로 진행한다.
1. 빈칸의 위치정보를 담은 배열에서 가장 앞에 있는 위치를 가져온다.
2. 그 위치에 1에서부터 9까지 중에, 위 3가지와 겹치지 않는 수(가능한 수)가 있으면
빈칸을 해당 수로 채우고 다음 빈칸 위치로 이동한다.
3. 2번과 같은 행동을 가능한 수가 하나라도 존재하지 않거나,
맵의 끝까지 탐색할 때까지 반복한다(재귀함수 호출).가능한 수가 없어 종료되면,
해당 함수를 호출한 함수로 돌아가 그다음 가능한 수로 다시 한번 2번 행위를 반복한다.
4. 재귀함수의 끝까지 갔을 때(빈칸을 다 탐색한 경우),
모든 빈칸이 메꿔진 상태이므로 스도쿠가 성공한 것이다. 그러므로 맵을 출력 한다.
말로 표현하다 보니 어려운데, 이를 그림으로 알기 쉽게 나타내보겠다.
간략하게 알아보기 위해서 4x4 스도쿠로 진행하도록 하겠다.
어차피 알고리즘 방식은 같으니까 크게 상관없다.
위 상태는 전체 맵에 대해서 탐색을 하는 것이 아닌 0이라고 적힌 빈칸에 대해서만 탐색을 하기 때문에
빈칸의 위치 정보를 따로 추출해 리스트에 저장해 뒀다는 의미로 다른 색으로 두었다.
이제 탐색을 시작한다.
순차적으로 빈칸 배열을 담았기 때문에 왼쪽 위부터 훑는다.
주황색으로 표기한 것은 현재까지 진행한 빈칸 리스트 현황이다.
해당 칸에서는 1부터 시작하여 4까지 중에 3이 존재하지 않기 때문에 3을 넣고 다음 빈칸 요소를 호출한다.
그렇기 때문에 동일하게 같은 연산으로 다음 빈칸에도 3이 나온다.
왼쪽부터 순차적인 과정이다.
위에서 설명했던 것에 반복이기 때문에 쭉 나열했다.
여기까지는 아무런 문제 없이 진행된다.
진행하다 보니 1 ~ 4까지 그 어떤 수도 넣을 수 없게 돼버렸다.
이 순간이 바로 앞에서 넣은 이 수들의 조합이 틀렸다는 증거가 되는 것이다.
그렇기 때문에 이 재귀함수를 종료하고 앞에서 다른 숫자를 택해서
다른 조합으로 다시 탐색해야 한다.
왼쪽부터 보면 되는데, 위 그림들이 뜻하는 것은 위 재귀함수를 호출했던 함수들로 돌아가,
빈칸을 1 ~ 4 중 해당 숫자를 채웠던 시점으로 가는 것이다.
그리고 똑같이 그다음을 검사한다.
그렇게 쭉 돌아가다 보면 왼쪽 두 개는 적당한 게 없어서 맨 오른쪽까지 돌아가버린다.
맨 오른쪽까지 돌아가면 4를 채울 수 있고 이제 다시 진행할 수 있다.
그 후 과정을 동일한 과정을 스도쿠의 빈칸을 모두 채울 때까지 진행한다.
그럼 위와 같은 그림이 나올 것이다.
이제 해당 알고리즘을 코드로 구현해 보겠다.
해당 코드에서 위의 백트래킹을 구현하는 것도 중요하지만
3가지 정보의 그룹을 어떻게 구성하는가도 중요한 관건이다.
문제 구현 단계
int map[10][10];
// 가능한 수인가?(중복 체크)
bool isPossible(int x, int y, int k){
for(int i = 1; i <= 9; i++){
// 같은 행 체크
if(map[x][i] == k && i != y) return false;
// 같은 열 체크
if(map[i][y] == k && i != x) return false;
// 같은 3x3 사각형 체크
int nx = (x-1)/3*3 + 1 +(i-1)/3;
int ny = (y-1)/3*3 + 1 + (i-1)%3;
if(map[nx][ny] == k && !(nx == x && ny == y)) return false;
}
return true;
}위에서 언급한 3가지 정보이다.
위에서부터 같은 행, 같은 열, 3x3 사각형이다.
같은 행과 같은 열은 그냥 1~9까지 번호를 매기고
해당 칸의 같은 가로 전체와, 세로 전체를 다 체크하면 된다.
헷갈리는 건 3x3 직사각형을 구현하는 건데, 이건 그냥 한번 보길 바란다.
여기서 해당 반복마다 조건문을 두어 k값이 있을 때는 false를 반환하게 하였다.
물론 좌표가 자기 자신일 때는 예외처리했다.
아무것도 중복되는 것이 없어야 true가 반환된다.
int map[10][10];
vector<pair<int,int>> empties;
// 백트래킹 함수
void backTracking(int idx){
// 빈칸을 다 채웠다면(빈칸 배열 끝까지 진행)
if(idx == empties.size()) {
printNumber();
exit(0);
}
int x = empties[idx].first;
int y = empties[idx].second;
for(int k = 1; k <= 9; k++){
// k가 가능한 수일때만
if(isPossible(x,y,k)){
map[x][y] = k;
backTracking(idx+1);
// 다른 수도 사용할 수 있도록 할당 해제
map[x][y] = 0;
}
}
return;
}백트래킹을 재귀호출하는 함수이다.
매개변수로 빈칸 좌표를 담고 있는 배열의 인덱스를 인자로 받는다.
k가 1 ~ 9까지인데, 사전순이기 때문에 1부터 시작하는 것이다.
빈칸에 가능한 수를 채울 수 있을 때만 재귀함수를 호출하도록 한다.
그렇기 때문에 빈칸이 하나라도 남는다면 빈칸의 개수만큼 idx가 될 수가 없다.
즉, idx가 빈칸 배열의 개수와 같다는 뜻은, 스도쿠가 완성됐다는 뜻이므로 스도쿠를 출력한다.
여기서 또 하나 봐야 할 것은
재귀함수를 호출하고 해당 함수가 끝나면 해당 빈칸에 넣어줬던 k를 다시 빈칸으로 만들어줘야 한다.
왜냐하면 이건 이 경우의 수에만 채워진 것이기 때문에
그대로 빈칸이 채워져 있으면 다른 경우의 수에 영향을 주기 때문이다.
설명은 끝났으므로 아래 전체 코드를 올리고 설명을 끝내겠다.
#include <iostream>
#include <string>
#include <vector>
#include <utility>
using namespace std;
int map[10][10];
vector<pair<int,int>> empties;
// 스도쿠 출력
bool printNumber(){
for(int i = 1; i <= 9; i++){
for(int j = 1; j <= 9; j++) cout << map[i][j];
cout << '\n';
}
return true;
}
// 가능한 수인가?(중복 체크)
bool isPossible(int x, int y, int k){
for(int i = 1; i <= 9; i++){
// 같은 행 체크
if(map[x][i] == k && i != y) return false;
// 같은 열 체크
if(map[i][y] == k && i != x) return false;
// 같은 3x3 사각형 체크
int nx = (x-1)/3*3 + 1 +(i-1)/3;
int ny = (y-1)/3*3 + 1 + (i-1)%3;
if(map[nx][ny] == k && !(nx == x && ny == y)) return false;
}
return true;
}
// 백트래킹 함수
void backTracking(int idx){
// 빈칸을 다 채웠다면(빈칸 배열 끝까지 진행)
if(idx == empties.size()) {
printNumber();
exit(0);
}
int x = empties[idx].first;
int y = empties[idx].second;
for(int k = 1; k <= 9; k++){
// k가 가능한 수일때만
if(isPossible(x,y,k)){
map[x][y] = k;
backTracking(idx+1);
// 다른 수도 사용할 수 있도록 할당 해제
map[x][y] = 0;
}
}
return;
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
for(int i = 1; i <= 9; i++){
string str;
cin >> str;
for(int j = 1; j <= 9; j++) {
map[i][j] = str[j-1]-'0';
if(map[i][j] == 0) empties.push_back(make_pair(i,j));
}
}
backTracking(0);
}시행착오
백트래킹을 처음 풀어봤다. 이렇게까지 어려운 것인지 처음 알았다.
답을 보고 나름대로 코드를 짜봤는데도 이해하기가 복잡했다.
역시 아직 기초가 많이 부족한 것 같다.
백트래킹 문제를 좀 많이 풀어봐야 할 것 같다.
뿐만 아니라 사각형에 가두는 것과 벡터에 segmentFault가 뜨는 것 등등의 그냥 구현적으로도 문제가 많았다.
그냥 기초 문법이 부족한 것 같다.