문제
스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.
위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.
하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.
입력
9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.
출력
9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.
제한
12095번 문제에 있는 소스로 풀 수 있는 입력만 주어진다.
C++17: 180ms
Java 15: 528ms
PyPy3: 2064ms
풀이
문제 자체는 간단하다.
살아가면서 한번쯤은 해봤을 듯한 스도쿠를 풀면 되는 문제이다.
다만 이 문제를 접근할때 생각해 봐야 될 점은 내생각으로는 시간복잡도이다.
공간은 최대 9 * 9 의 배열만 나오니 크게 신경쓰지 않아도 되지만, 만약 나이브하게 생각해보면 한 칸에 1~9까지 들어갈 수 있고, 81개의 칸이 있으므로 9^81의 시간이 나오게 된다.
이렇게되면 이 문제를 2초안에 푸는 것은 불가능해진다.
하지만 막상 이 문제를 구현해보면, 3 * 3 격자의 겹치는 숫자와, 같은 행, 열에 겹치는 숫자를 제외하게 된다면 생각보다 가지가 많이 쳐진다는 것을 생각해 낼 수 있다.
모든 칸이 0인 경우가 가장 큰 시간복잡도를 가지게 된다.
이 경우를 생각해보면 첫번째 칸(좌측 최상단에서 우측으로 이동)에 올 수 있는 숫자의 개수는 9가지, 다음은 8가지 , 다음은 7가지, ~ 1가지까지 가고 그 다음 행에는 이미 전 행이 채워져있으므로 6가지, 다음은 5가지, ~ 1가지 까지 채우면 막상 게산해보았을때 9! = 362880, 나머지 8개의 행은 무조건 9!보다 작은 경우가 나올 수 밖에 없으므로 시간이 충분하다는 것을 알 수 있다.
그리고 81자리의 숫자가 가장 작은 경우를 출력해야하는데, 백트래킹을 구현할때 '0'인 칸에 1~9까지 순차적으로 넣어본다면 자동적으로 가장 작은 경우가 나올 수 밖에 없다.
간단히 하기 위해 모든 칸에 채워졌을때 exit(0)을 사용하였다.
정답 코드
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
string board[9];
vector<pair<int,int>>v;
void func(int n){
if(n == v.size()){
for(int i=0; i<9; i++)
cout<<board[i]<<'\n';
exit(0);
}
pair<int,int>point = v[n];
int arr[11]={0};
for(int i=0; i<9; i++){
arr[board[point.first][i]-'0'] = 1;
arr[board[i][point.second]-'0'] = 1;
}
for(int i = (point.first/3)*3; i<(point.first/3)*3+3; i++)
for(int j = (point.second/3)*3; j<(point.second/3)*3+3; j++)
arr[board[i][j]-'0'] = 1;
for(int i=1; i<=9; i++){
if(arr[i]) continue;
board[point.first][point.second] = i+'0';
func(n+1);
board[point.first][point.second] = '0';
}
}
int main(){
for(int i=0; i<9; i++){
cin>>board[i];
}
for(int i=0; i<9; i++)
for(int j=0; j<9; j++)
if(board[i][j] == '0')
v.push_back({i,j});
func(0);
}
