백준 2239: 스도쿠

문제
스도쿠 성공다국어
 
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 256 MB 9402 4661 3428 48.686%
문제
스도쿠는 매우 간단한 숫자 퍼즐이다. 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
예제 입력 1 
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107
예제 출력 1 
143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127
사고 과정
스도쿠 문제
전형적인 back트래킹문제라는데, 난 일단 안풀어봤다.n-queens같은건 몇 개 풀어봤다
스도쿠 자체를 한번도 안해봤따.

가로줄 쫘악 탐색하고 세로줄 쭈욱 탐색해서 
없는 숫자를 놓으면 되는 것일까?
숫자를 놓고 dfs를 계속 돌리면 되는 것일깡?
감이온당
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

dfs를 어떻게 짜면 될까.
문제를 다시보니 작은 사각형안의 9개의 숫자도 겹치면 안된다.
난감쓰,,
0    1    2    3    4    5    6    7    8
9    10  11   12  13  14   15  16  17
18  19   20   21 22  23   24   25  26
이런식으로 배열이 구성된다고 생각하면
9로 나누면 y값
9로 모듈러 해주면 x값이 나온다
EX1)26
y=2, x=8
26/9 =2
26%9 =8
EX2) 12
y =1,x=3
12/9=1
12%9=3
이런식으로 좌표를 잡으면 된다.
#include <iostream>
#include <string>
using namespace std;
bool finish = false;
int arr[9][9];

void sdokue(int num) {
if (finish) return;
if (num == 81) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++)
cout << arr[i][j];
cout << '\n';
}
finish = true;
return;
}
int y = num / 9;
int x = num % 9;
if (arr[y][x] != 0) sdokue(num + 1);//0이 아니면 이미 값이 들어있기때문에 다음 자리로 넘어가주면 된다.
else {
for (int i = 1; i < 10; i++) {//1부터 돌려가면서 확인해주고
bool check = true;
for (int j = 0; j < 9; j++) {
if (arr[y][j] == i || arr[j][x] == i) {
check = false;
break;
}
}//행과 열에 넣으려는 숫자가 있나 따져줌
if (!check) continue;//있으면 continue
int ny = (y / 3) * 3;//8을 3으로 나누면 2, 2에서 3을 곱하면 6  그럼 밑에 이중포문에서6~8까지의 인덱스를 검사하게된다.
int nx = (x / 3) * 3;
for (int j = ny; j < ny + 3; j++) {
for (int k = nx; k < nx + 3; k++) {
if (arr[j][k] == i) {//만약 있으면
check = false;//false해주고
break;
}
}
if (!check) break;
}
if (check) {
arr[y][x] = i;
sdokue(num + 1);
arr[y][x] = 0;
}
}
}
}

int main() {
string s;
for (int i = 0; i < 9; i++) {
cin >> s;
for (int j = 0; j < 9; j++)
arr[i][j] = s[j] - '0';
}
sdokue(0);
return 0;
}