글 읽기 - 시간복잡도 계산이 잘안되네요...

superm 5년 전 0

흑...도와주십쇼...ㅠㅠ

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 9
#define INF 987654321
using namespace std;
typedef pair<int,int> node;

int map[MAX][MAX];
vector<node> blank;

bool chk_row(int r,int c,int num){
    for(int i=0; i<9; i++){
        if(map[i][c] == num) return false;
    }
    return true;
}

bool chk_col(int r,int c,int num){
    for(int i=0; i<9; i++){
        if(map[r][i] == num) return false;
    }
    return true;
}

bool chk_box(int r,int c,int num){
    int row = r - (r % 3);
    int col = c - (c % 3);
    
    for(int i=row; i<row+3; i++){
        for(int j=col; j<col+3; j++){
            if(map[i][j] == num) return false;
        }
    }
    return true;
}

bool is_possible(int r,int c,int num){
    // 만약 행,열,박스 모두 해당 숫자가 없다면 해당 빈칸에 숫자 넣을 수 있음
    if(chk_row(r,c,num) && chk_col(r,c,num) && chk_box(r,c,num)){
        return true;
    }
    return false;
}

void printSdoku(){
    // 스도쿠 출력
    for(int i=0; i<9; i++){
        for(int j=0; j<9; j++){
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
}

void dfs(int ind,int cnt){
    int i = blank[ind].first;
    int j = blank[ind].second;
    
    // 스도쿠의 모든 빈 칸을 채웠다면
    if(cnt == blank.size()){
        printSdoku();
        exit(0);
    }
    
    // 빈 칸에 1~9 까지의 경우를 넣음
    // 스도쿠는 빈 칸이 존재할 수 없기 때문에, vector 를 반복문으로 넣지 않음
    for(int num=1; num<=9; num++){
        // i 가 빈 칸에 들어갈 수 있는지 확인
        if(is_possible(i,j,num)){
            map[i][j] = num;
            dfs(ind+1,cnt+1);
            map[i][j] = 0;
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    // 스도쿠 입력
    for(int i=0; i<9; i++){
        for(int j=0; j<9; j++){
            cin >> map[i][j];
            // 빈 칸이라면 black 벡터에 push
            if(map[i][j]==0) blank.push_back(node(i,j));
        }
    }
    
    dfs(0,0);
}

이런 코드는 상한선을 적당히 계산할 수는 있겠지만 보드의 상태에 따라 너무나 많은 커팅이 일어나기 때문에 실제로 도는 속도와는 비교가 불가능할 것 같습니다. 커팅이 없다고 가정했을 때 각 줄에서 선택할 수 있는 수가 9가지씩이라고 가정하면 9^81이지만 실제로는 같은 행, 열, 3x3 사각형 내에 같은 수가 없는지를 체크하고 잘라내는 일들이 너무나 예측할 수 없게 발생하기 때문에 이 상한선은 크게 의미가 없습니다.

https://en.wikipedia.org/wiki/... 에서도 백트래킹 기법에 대해 설명하고 있지만 시간복잡도에 대한 이야기는 하지 않습니다.

superm 5년 전 0

djm03178 님 답변 정말 감사합니다 !!!

저도 9^81 이라 생각해서 긴가민가 했는데 답변을 보고 이해할 수 있었습니다 ㅎㅎ

친절한 답변 너무 감사드립니다 !!

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

문제

문제

출처

ICPC

시간복잡도 계산이 잘안되네요...

superm 5년 전 0

djm03178 5년 전 1

superm 5년 전 0

djm03178 님 답변 정말 감사합니다 !!!

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말