[백준] 2580 스도쿠

이 문제가 왜 골드 4인지 잘 모르겠다..ㅋ

 

빈칸에 전부 다 대입을 한 후 반복문을 돌리면서 확인하는 경우의 수는 너무 많이 나오고 시간초과가 발생할 확률이 매우 높다.

따라서 빈칸에 적당한 값을 넣기 전에 같은 행, 열, 블록을 검사한 후 같은 숫자가 없는 경우 대입하는 방법으로 문제를 해결해야 한다.

 

 

 

 

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> input2580(10,vector<int>(10,0));
vector<pair<int, int>> zeroPos2580;
bool complete2580 = false;

bool checkValidSudo(int x, int y){
    
    // 세로 가로줄 검사
    for(int i=1; i<=9; ++i){
        if(input2580[x][y] == input2580[i][y] and x != i)
            return false;
        if(input2580[x][y] == input2580[x][i] and y != i)
            return false;
    }
    
    // 블록 내부 검사
    int rowX = (x-1)/3;
    int colY = (y-1)/3;
    
    for(int i=3*rowX+1; i<=3*rowX+3; ++i){
        for(int j=3*colY+1; j<=3*colY+3; ++j){
            if(i==x && j == y)
                continue;
            if(input2580[i][j] == input2580[x][y])
                return false;
        }
    }
    
    return true;
}

void backback2580(int count){
    
    if(count == zeroPos2580.size()){
        for(int i=1;i<=9; ++i){
            for(int j=1;j<=9; ++j)
                cout<<input2580[i][j]<<" ";
            cout<<"\n";
        }
        complete2580 = true;
        return;
    }
    
    int x = zeroPos2580[count].first;
    int y = zeroPos2580[count].second;
    for(int i=1; i<=9; ++i){
        input2580[x][y] = i;
        if(checkValidSudo(x, y))
            backback2580(count+1);
        
        if(complete2580)
            return;
    }
    input2580[x][y] = 0;
}

void sudoku2580(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    for(int i=1;i<=9; ++i){
        for(int j=1;j<=9; ++j){
            int a; cin>>a;
            input2580[i][j] = a;
            if(a==0)
                zeroPos2580.push_back({i,j});
        }
    }
    
    backback2580(0);  
}