[백준 2239] 스도쿠 (C++)

이 문제는 가능한 모든 경우의 수를 탐색해보는 방법 밖에 없다. 그런데, 문제 조건에 맞추어 스도쿠를 풀어야하므로 백트래킹이 적절해보인다.

입력으로 들어온 퍼즐의 0인 칸에 적절한 값을 채워넣어야 한다. 그래서 재귀함수 내부에서 0인 점을 $O(N^2)$으로 찾은 후에, 행, 열, 3x3칸에 중복된 숫자가 있는지 확인하고 값을 채워 넣은 뒤 재귀 호출을 하는 경우를 생각해보자.

하지만, 문제에서 C++의 경우에는 180ms이내에 처리되어야 AC를 받을 수 있다.

가장 첫번째 케이스를 찾아서 출력하면 된다지만, 시간 초과가 발생할 여지가 있다.

따라서, 0인 칸을 곧바로 찾을 수 있도록 벡터에 넣어 관리하자.

그리고, 행, 열, 해당 칸이 속하는 3x3 크기의 보드에 숫자가 중복되는지 확인해야 하므로 isUsed배열을 사용하자.

isUsed[0][i][k]은 i행에 k가 존재하는지, isUsed[1][j][k]은 j열에 k가 존재하는지, isUsed[2][3 * (i / 3) + (j / 3)][k]는 3x3 보드에 k가 존재하는지 여부를 저장하고 있다.

따라서, i행 j열은 위 3가지 값이 모두 false인 경우에만 k값을 저장할 수 있다.

이후, 재귀함수를 호출하고 원상태로 롤백해줘야 정상적인 탐색이 가능하다.

이를 코드로 옮기면 아래와 같다.

#include <bits/stdc++.h>
using namespace std;

const int N = 9;
int board[N][N];
bool isUsed[3][N][10];
vector<pair<int, int>> zeros;

void bt(int idx) {
    if (idx == zeros.size()) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++)
                cout << board[i][j];
            cout << "\n";
        }
        exit(0);
    }

    int i = zeros[idx].first;
    int j = zeros[idx].second;

    for (int k = 1; k < 10; k++) {
        if (isUsed[0][i][k] || isUsed[1][j][k] || isUsed[2][3 * (i / 3) + (j / 3)][k])
            continue;
        board[i][j] = k;
        isUsed[0][i][k] = 1;
        isUsed[1][j][k] = 1;
        isUsed[2][3 * (i / 3) + (j / 3)][k] = 1;
        bt(idx + 1);
        isUsed[0][i][k] = 0;
        isUsed[1][j][k] = 0;
        isUsed[2][3 * (i / 3) + (j / 3)][k] = 0;
        board[i][j] = 0;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    for (int i = 0; i < N; i++) {
        string line;
        cin >> line;
        for (int j = 0; j < N; j++) {
            board[i][j] = line[j] - '0';
            if (!board[i][j]) {
                zeros.push_back({i, j});
            }
            isUsed[0][i][board[i][j]] = 1;                     // 행
            isUsed[1][j][board[i][j]] = 1;                     // 열
            isUsed[2][3 * (i / 3) + (j / 3)][board[i][j]] = 1; // 3x3
        }
    }

    bt(0);
}