글 읽기 - 시간초과가 납니다

dmswl022329 3년 전 0

모든 경우를 찾아가는 느낌이 물씬 들어서

어떻게 하면 스도쿠를 채운뒤 모든 행동을 중지하고 출력만 하고 끝낼 수 있을까요

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

bool y[9][10];// v[i].first 행에있는 숫자의 정보 1~9 있으면 true 없으면 false
bool x[9][10];// v[i].second 열에있는 숫자의 정보 1~9 있으면 true 없으면 false
bool s[9][10];// (y/3)*3+x/3 각 칸에 있는 숫자의 정보 1~9 있으면 true 없으면 false
//0 1 2
//3 4 5
//6 7 8 의 느낌으로 저장
int sudoku[9][9];
vector<pair<int,int>> v;// 0의 인덱스를 페어로 저장 first에 행 second에 열
vector<int> num;// 0인 인덱스에 들어갈 숫자

void btk(){
    if(num.size()==v.size()){//v와 num의 수가 같아지면 모든칸에 숫자가 채워진것이므로 sudoku배열에 입력하고 종료한다
        for(int p=0;p<v.size();p++){
            sudoku[v[p].first][v[p].second]=num[p];
        }
        return;
    }
    for(int i=num.size();i<v.size();i++){//num에 숫자가 채워지면 다음 좌표를 보기위해 i의 시작을 num의 크기로 설정
        for(int N=1;N<=9;N++){//1~9중 무엇이 들어갈지 정함
            if(!y[v[i].first][N]&&!x[v[i].second][N]&&!s[(v[i].first/3)*3+v[i].second/3][N]){
                num.push_back(N);//들어갈 숫자를 num에 저장
                y[v[i].first][N]=1;
                x[v[i].second][N]=1;
                s[(v[i].first/3)*3+v[i].second/3][N]=1; // 그 인덱스의 정보를 바꿈
                btk();// 다음 0을 채우기 위해 백트래킹
                y[v[i].first][num.back()]=0;
                x[v[i].second][num.back()]=0;
                s[(v[i].first/3)*3+v[i].second/3][num.back()]=0; // 백트래킹이 끝나면 들어간 값의 정보를 제거
                num.pop_back();// 숫자를 없앤다
            }
        }
    }
}

int main(){
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            cin >> sudoku[i][j];
            if(sudoku[i][j]==0){//입력을 받음과 동시에 정보를 저장 0이면 v에 아니면 y, x, s에
                v.push_back({i,j});
            }else{
                y[i][sudoku[i][j]]=1;
                x[j][sudoku[i][j]]=1;
                s[(i/3)*3+j/3][sudoku[i][j]]=1;
            }
        }
    }
    btk();
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            cout << sudoku[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

39dll 3년 전 1

exit 함수에 대해 알아보시면 될 것 같습니다.

dmswl022329 3년 전 0

백트래킹뒤에 조건에따라 return;을 하니 통과하네요!

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

문제

문제

출처

ICPC

시간초과가 납니다

dmswl022329 3년 전 0

39dll 3년 전 1

dmswl022329 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말