글 읽기 - 시간초과 해결방법

ks610126ks 1년 전 0

시간초과 해결방법이 무었일지 궁금합니다.

또한 제 코드는 왜 시간 초과 에러가 발생하는지도 궁금합니다.

#include<iostream>
#include<string>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;


int board[82];
int X,Y;
int cnt=0;
void position(int x){
    X = x/9;
    Y = x%9;
    
}

void printfff(){
    for(int i=0; i<81;i++){
        cout << board[i] << " ";
        if((i+1)%9==0)
            cout<< endl;
    }
}

int sum_col(int x){
    int sum=1+2+3+4+5+6+7+8+9;
    for(int i=0;i<9;i++){
        if(!board[9*i+Y]) return 1;
        sum-=board[9*i+Y];
    }
    if(!sum)return 1;
    else return 0;
}
int sum_row(int x){
    int sum=1+2+3+4+5+6+7+8+9;
    for(int i=0;i<9;i++){
        if(!board[i+X*9])return 1;
        sum-=board[i+X*9];
    }
    if(!sum)return 1;
    else return 0;
        
}
int sum_sq(int x){
    int sum=1+2+3+4+5+6+7+8+9;
    int xx =X/3;
    int xy =X%3;
    for(int i=0;i<3;i++)for(int j=0;j<3;j++){
        if(!board[i+ (3*xx*9+((xy+j)%3)*9)  +(Y/3)*3]){
            return 1;
        }
            sum-=board[i+ (3*xx*9+((xy+j)%3)*9)  +(Y/3)*3];
    }
    
    
    
    if(!sum)return 1;
    else return 0;
}

int check(int x){
    position(x);// x,y값 반환
    
    if(sum_col(x)&&sum_row(x)&& sum_sq(x)){
        return 1;
    }else return 0;
}


int sudocu(int x){
    if(x == 81){
        printfff();
        exit(0);
    }else{
        for(int i = 1; i <= 9; i++){
            if(board[x]==0){
                board[x] = i;
                if(check(x)){
                    sudocu(x+1);
                    board[x]=0;
                }
                else{
                    board[x]=0;
                }
                
                //cout << endl;
                //cout << endl;
                //cout<< x << endl;
                //printfff();
                //cout << endl;
                //cout << endl;
            }else{
                sudocu(x+1);
            }
                
        }
    }
    return 1;
}


int main() {
    
    for(int i=0; i<81;i++){
        int temp;
        
        cin >> temp;
        board[i]=temp;
        if(!temp){
            cnt++;
        }
    }
    sudocu(0);
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 해결방법

ks610126ks 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말