글 읽기 - 스도쿠 시간초과 질문입니다. (next_permutation 사용 시)

coacervate 4년 전 0

최대한 시간을 줄여본다고 애썼는데, 11%에서 시간초과가 납니다.

구현 방식은

1. 처음에 행(row) 별로 빠져있는 숫자에 대해 candidate 를 만들고, 빠진 위치를 omit_coord에 열(column) 값만 저장했습니다.

2. 백트래킹 함수는 0행으로 시작해서, 매 행마다 위에서 만들어놓은 candidate를 next_permutation을 이용해 계속 위치를 수정하여 뿌립니다.

3. 2번에서 값을 뿌리면서 열, 그리고 블록의 값과 겹치는지 확인 후, 만약 겹친다면 다음 next_permutation으로 넘어가고, 겹치지 않는다면 해당 row를 선택하고 다음 row로 넘어갑니다. (재귀 호출)

4. 이렇게 계속 해서 0~8행을 다 보고 row 값이 9가 되면, 2, 3의 과정을 통해 매 행마다 유효성 검사를 하였으므로, 별다른 검사 없이 전체 table을 출력하고 프로그램을 종료합니다.

5. 만약 어떤 row에서 유효성 조건을 충족하지 못 해 더 이상 넘어 갈 수 없는 경우, 3번으로 다시 돌아가 다음 next_permutation으로 넘어갑니다 (백트래킹)

이렇게 생각을 해 보았는데요, 질문 게시판에 있는 TC를 여러 개 돌려본 결과 답이 다 나오는 것 같습니다. (0으로만 채워져 있는 것 포함)

시간 복잡도는 9! ^ 9!.....인것 같긴 한데 이렇게 푸는 게 아예 잘못된 걸까요 ㅠㅠ

제 코드에서 어느 부분이 시간을 많이 잡아먹는지 알고 싶습니다.

+ 시간초과 나는 TC를 알고 싶습니다...

// BOJ ID 2580 (SUDOKU)
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
//#include <set>
using namespace std;

int table[9][9];
vector<vector<int>> candidate(9);
vector<vector<int>> omit_coord(9);
//set<int> check_y[9], check_block[9];

int check_y[9][10], check_block[9][10];
// 9개의 열, 9개의 블록, 각 열과 블록마다 0부터 9까지의 수

inline void print_table(){
    for(int i=0;i<9;++i){
        for(int j=0;j<9;++j){
            printf("%d ", table[i][j]);
        }
        printf("\n");
    }
}

void sudoku(int row){
    if(row == 9){
        print_table();
        exit(0);
    }

    int size = candidate[row].size();
    
    //vector<int> tmp = candidate[row];

    int tti;
    bool test;
    do{
        tti = 0;
        test = true;

        for(auto i:omit_coord[row]){
            table[row][i] = candidate[row][tti];
            tti ++;

            // verify procedure

            if(check_y[i][table[row][i]] != 0){
                test = false;
                break;
            }

            if(check_block[3*(row/3)+(i/3)][table[row][i]] != 0){
                test = false;
                break;
            }
        }
        
        if(test){
            for(auto i:omit_coord[row]){
                check_y[i][table[row][i]] = 1;
                check_block[3*(row/3)+(i/3)][table[row][i]] = 1;
            }

            sudoku(row+1);

            // 안 되는 경우 복구1
            for(auto i:omit_coord[row]){
                check_y[i][table[row][i]] = 0;
                check_block[3*(row/3)+(i/3)][table[row][i]] = 0;
            }
        }

        // 안 되는 경우 복구2
        for(auto i:omit_coord[row]){
            table[row][i] = 0;
        }
        
    }while(next_permutation(candidate[row].begin(), candidate[row].end()));

    //candidate[row] = tmp;
}

int main(){
    int check[10];
    for(int i=0;i<9;++i){
        memset(check, 0, sizeof(check));
        for(int j=0;j<9;++j){
            scanf("%d", &table[i][j]);
            if(table[i][j] != 0){ // 열, 구역별 체크
                check_y[j][table[i][j]] = 1;
                check_block[3*(i/3)+(j/3)][table[i][j]] = 1;
            }
            check[table[i][j]] = 1;
            if(table[i][j] == 0){
                omit_coord[i].push_back(j);
            }
        }
        for(int j=1;j<10;++j){
            if(check[j] == 0){
                candidate[i].push_back(j);
            }
        }
    }

    sudoku(0);
    return 0;
}

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