BOJ 2239 - 스도쿠

https://www.acmicpc.net/problem/2239

 

접근법

백트래킹 연습용으로 널리 퍼져있는 문제이다.

스도쿠 빈칸에 알맞은 번호를 넣으면, 이 번호에 의해 다른 빈칸에 무엇이 들어가는지 결정된다.

따라서, 만약 이전 선택이 잘못됐을 경우 돌아가야한다.

이를 백트래킹을 이용해 구할 수 있다.

보다 구체적으로 설계를 해보자.

 

1. 빈칸을 돌면서 해당 빈칸에 들어갈 적절한 번호를 선별한다.

2. 선별된 번호를 빈칸에 넣고, 재귀적으로 다음 빈칸을 수행한다.

3. 만약 빈칸을 모두 매꾸었으면 정답이므로 배열을 출력한다.

4. 만약 이후의 빈칸에 적절한 숫자를 넣을 수 없는 경우, 재귀를 종료하여 이전으로 돌아가도록한다.

 

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>

#define ll long long
using namespace std;

char tmp[10][10];
int arr[10][10];
vector<pair<int, int> > blank;

bool vertical_check(int y, int value) {
    for (int i = 0; i < 9; i++) {
        if (arr[i][y] == value) {
            return false;
        }
    }
    return true;
}

bool horizonal_check(int x, int value) {
    for (int i = 0; i < 9; i++) {
        if (arr[x][i] == value) {
            return false;
        }
    }
    return true;
}

bool cube_check(int x, int y, int value) {
    int sx = x / 3 * 3;
    int sy = y / 3 * 3;

    for (int i = sx; i < sx + 3; i++) {
        for (int j = sy; j < sy + 3; j++) {
            if (arr[i][j] == value) {
                return false;
            }
        }
    }
    return true;
}

void func(int blank_idx) {
    if (blank_idx == blank.size()) {
        for(int i=0;i<9;i++) {
            for(int j=0;j<9;j++) {
                cout << arr[i][j];
            }
            cout << endl;
        }
        exit(0);
    }

    for (int i = 1; i < 10; i++) {
        int x = blank[blank_idx].first;
        int y = blank[blank_idx].second;
        // cout << "idx: " << blank_idx<< endl;
        // cout << "x, y: " << x << ", " << y << endl << endl;

        if (
            vertical_check(y, i) &&
            horizonal_check(x, i) &&
            cube_check(x,y,i)
        ) {

            arr[x][y] = i;
            func(blank_idx + 1);
            arr[x][y] = 0;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> tmp[i][j];
            arr[i][j] = (int)(tmp[i][j] - '0');
            if (arr[i][j] == 0) {
                blank.push_back({i, j});
            }
        }
    }

    func(0);

    return 0;
}