Baekjoon 2239번 스도쿠

문제

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

걸린 시간

-

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int num[10];
int sudoku[9][9];
vector<pair<int, int>> blank; // y, x

void print(){
    for(int y = 0; y < 9; y++){
        for(int x = 0; x < 9; x++){
            printf("%d", sudoku[y][x]);
        }
        printf("\n");
    }
    exit(0);
}

vector<int> available(int y, int x){
    vector<int> ret;
    memset(num, 0, sizeof(num));
    // row
    for(int r = 0; r < 9; r++)
        if(sudoku[r][x])
            num[sudoku[r][x]] = 1;
    // col
    for(int c = 0; c < 9; c++)
        if(sudoku[y][c])
            num[sudoku[y][c]] = 1;
    // box
    for(int r = (y/3)*3; r < (y/3)*3+3; r++)
        for(int c = (x/3)*3; c < (x/3)*3+3; c++)
            if(sudoku[r][c])
                num[sudoku[r][c]] = 1;
    // return
    for(int i = 1; i <= 9; i++)
        if(!num[i])
            ret.push_back(i);
    return ret;
}

void solve(int idx){
    // 기저 사례
    if(idx == blank.size()) print();
    // 재귀 호출
    int y = blank[idx].first;
    int x = blank[idx].second;
    vector<int> candidate = available(y, x);
    for(int i = 0; i < candidate.size(); i++){
        sudoku[y][x] = candidate[i];    
        solve(idx+1);
        sudoku[y][x] = 0;
    }
}

int main(){
    for(int y = 0; y < 9; y++){
        for(int x = 0; x < 9; x++){
            scanf("%1d", &sudoku[y][x]);
            if(!sudoku[y][x])
                blank.push_back(make_pair(y, x));
        }
    }
    solve(0);
    return 0;
}

백트래킹;퇴각검색은 은연중에 사용하고 있었던 완전탐색의 한 종류였다.