백준 2580번 스도쿠_ 백트래킹(BackTracking) (c++)

문제: https://www.acmicpc.net/problem/2580

2580번: 스도쿠

 

이번 문제는 백트래킹에 관한 문제입니다! 백트래킹은 단순히 모든 경우의 수를 조사하는 브루트포스(무차별대입)과는 다른 개념이에요.
모든 걸 다 조사하다가 틀린 게 발견되면 다시 처음부터 조사한다구요!

것보다 이번 스도쿠 문제를 풀면 앞으로 어떤 스도쿠 문제가 주어져도 1초만에 풀어낼 수 있을 생각을 하니 설렙니다 :)
자, 그러면 어떻게 백트래킹을 통해서 스도쿠문제를 해결할 수 있을까요?

간단합니다! (하지만 생각해내는 건 간단치 않죠...)
함수를 만들어서 매 빈칸(0)마다 1-9의 숫자를 넣어보면서 다음의 3가지를 물어보는 거에요.
(지금부터 해당 빈칸과의 대화입니다..)

" 1. 이 숫자가 너가 포함된 행에 혹시 있니? "
" 2. 이 숫자가 너가 포함된 열에 혹시 있니? "
" 3. 이 숫자가 너가 포함된 3*3 정사각형 안에 있니? " (3*3행렬은 전체 9*9판을 9조각 낸 게 기준이란 건 아시겠죠..)

" 세가지 조건 다 이 숫자가 포함안되어있다면 일단 그 숫자를 너에게 대입하고 다음거를 볼게! "
" 하지만 다른 거를 찾다가 너가 잘못된다는 걸 알면 다시 그 다음 숫자부터 대입해볼거야! "

어때요?! 이해가셨죠?
그리고 탐색 순서는 DFS(깊이 우선탐색)을 사용합니다.
이유는 뭘까요? 깊이 우선 탐색을 해야 해당 빈칸에 대해 쭉 탐색하다가 잘못되었다는 걸 알면 원래로 돌아올 수 있겠죠?

그럼 이제 이걸 코드로 어떻게 구현했는지 같이 보실까요?

#include<iostream>
#define MAX 9
#define square(x, y) ((x/3)*3+y/3)
using namespace std;
 
int sudoku[MAX][MAX];
bool Row[MAX][MAX+1];
bool Col[MAX][MAX+1];
bool Square[MAX][MAX+1];

void input();
void print_sudoku();
void DFS(int n);

int main(){
    input();
    DFS(0);
    return 0;
}

void input(){ //input을 받을 때마다 해당위치에 그 값이 존재한다는 걸 기록해놓을거에요.
    for (int i=0; i<MAX; i++){
        for (int j=0; j<MAX; j++){
            cin >> sudoku[i][j];
            if (sudoku[i][j] != 0){
                Row[i][sudoku[i][j]] = true; // i번째 Row에 sudoku[i][j]는 존재합니다.
                Col[j][sudoku[i][j]] = true; // j번째 Col에 sudoku[i][j]는 존재합니다.
                Square[square(i,j)][sudoku[i][j]] = true; // n번째 사각형에 sudoku[i][j]는 존재합니다.
            }
        }
    }
}

void print_sudoku(){
    for (int i=0; i<MAX; i++){
        for (int j=0; j<MAX; j++){
            cout << sudoku[i][j]<< " ";
        }
        cout << "\n";
    }
}

void DFS(int n){
    if (n==81) {
        print_sudoku();
        exit(0);
    }
    int x = n/MAX;
    int y = n%MAX;
    if (sudoku[x][y] == 0){
        for (int i=1; i<10; i++){
            if (!Row[x][i] && !Col[y][i] && !Square[square(x,y)][i])
            {
                Row[x][i] = Col[y][i] = Square[square(x,y)][i] = true;
                sudoku[x][y] = i;
                DFS(n+1);
                sudoku[x][y] = 0;
                Row[x][i] = Col[y][i] = Square[square(x,y)][i] = false;
            }
        }
    }
    else DFS(n+1);
}

이젠 어떤 스도쿠문제도 난 1초만에 풀 수 있다!!

끝!