[백트래킹] 백준 2580 스도쿠

 

백트래킹을 알고 있다면, 그대로 하면 풀린다!

원리는 간단하다, 모든 경우를 탐색하는 것인데

빈칸에 들어갈 수 있는 후보자를 찾은 뒤,

처음 후보자를 놓고, 다음 빈칸을 같은 방법으로 탐색한다.

그러다가 막히면(후보자가 없다거나) 다시 돌아오면 된다 (백트래킹!)

 

주의할 것은, 스페셜 져지문제인 만큼 답이되는 후보 제일 먼저 발견한 것을 찾으면, 바로 프로그램을 종료하면 된다.

<cstdlib> 헤더파일에 있는 exit(0)함수를 썼다.

 

후보자를 찾기 위해 가로세로를 탐색하고,

사각형을 탐색하는데 아이디어만 잘 내면 될 듯하다!

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <utility>
using namespace std;
int N = 9;
int a[9][9];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int dz[3][3] = {{0, 1, 2}, {-1, 0, 1}, {-2, -1, 0}};

vector<pair<int, int> > blanks;

vector<int> get_candidates(int x, int y){
    bool check[10] = {false, };

    // 1. 가로, 세로 확인
    for (int i=0; i<4; ++i){
        int nx = x + dx[i];
        int ny = y + dy[i];

        while(0 <= nx && nx < N && 0 <= ny && ny < N){
            int found = a[nx][ny];
            if (!check[found]) check[found] = true;
            nx += dx[i];
            ny += dy[i];
        }
    }
    // 2. 주변 사각형 확인
    int mod_x = x % 3;
    int mod_y = y % 3;
    for (int i=0; i<3; ++i){
        int nx = x + dz[mod_x][i];
        for (int j=0; j<3; ++j){
            int ny = y + dz[mod_y][j];
            if (0 <= nx && nx < N && 0 <= ny && ny < N){
                int found = a[nx][ny];
                if (!check[found]) check[found] = true;
            }
        }
    }
    
    vector<int> candidates;
    for (int i=1; i<10; ++i){
        if (!check[i]) candidates.emplace_back(i);
    }

    return candidates;
}

void solve(int depth){
    if (depth == (int)blanks.size()){
        for (int i=0; i<N; ++i){
            for (int j=0; j<N; ++j)
                printf("%d ", a[i][j]);
            puts("");
        }
        exit(0);
    }
    int x = blanks[depth].first;
    int y = blanks[depth].second;
    vector<int> candidates = get_candidates(x, y);
    for (int c=0; c<candidates.size(); ++c){
        a[x][y] = candidates[c];
        solve(depth + 1);
        a[x][y] = 0;
    }
}

int main() {
    for (int i=0; i<N; ++i) {
        for (int j=0; j<N; ++j) {
            scanf("%d", &a[i][j]);
            if (a[i][j] == 0)
                blanks.emplace_back(make_pair(i, j));
        }
    }
    solve(0);

    
    return 0;
}