글 읽기 - 백트래킹 시간복잡도 계산 질문입니다.

rlarlghks970113 4년 전 0

제가 짠 백트래킹 코드의 시간복잡도를 구해보려고 하는데요.

1. 시간복잡도를 정확하게 구했는지 궁금합니다.

한 변의 길이가 9이니 n을 9로 잡으면

(9 x 9 스도쿠 탐색) = n²

(한 좌표에서의 가능한 경우의 수 찾기) = lgn

O((lgn)ⁿ^*n)의 시간복잡도로 계산했는데 맞게 계산했는지 궁금합니다.

2. 백트래킹에서 최악의 경우 (한 좌표에서 가능한 경우의 수 찾기)가 lgn이 아니라 n=9가 될텐데 왜 모든 좌표가 0 0 0 .... 0 0 0 인 상황에서도 작동할 수 있는지도 궁금합니다.

3. 백트래킹 같은 경우 쓸모 없는 가지를 없애버리는 개념으로 알고 있는데 이럴 경우 시간복잡도를 구하는 법을 잘 모르겠습니다.

백트래킹에서 시간복잡도를 구하는 팁이 있다면 알려주세요 :)

#include <iostream>
#include <vector>
#include <set>

using namespace std;

vector<vector<int>> map(9, vector<int>(9, 0));

//가능한 숫자 저장

//좌표 별로 가능한 숫자 저장
set<int> possible[9][9];
//가로에 이미 존재하는 숫자
set<int> existing_hor[9];
//세로에 이미 존재하는 숫자
set<int> existing_ver[9];
//9칸 정사각형에 이미 존재하는 숫자
set<int> existing_rect[3][3];


//x, y : coordinates
bool backtracking(int x = 0, int y = 0)
{
    //다음 0 찾기
    for(int i = x; i < 9; ++i)
    {
        for(int j = 0; j < 9; ++j)
        {  
            //0을 찾았다면
            if(map[i][j] == 0)
            {
                set<int>::iterator iter;
                for(iter = possible[i][j].begin(); iter != possible[i][j].end(); ++iter)
                {
                    int next_value = *iter;
                    //넣어도 되는 숫자인지 체크
                    //가로 체크
                    if(existing_hor[i].find(next_value) != existing_hor[i].end()) continue;
                    //세로 체크
                    if(existing_ver[j].find(next_value) != existing_ver[j].end()) continue;
                    //9칸 정사각형 체크
                    if(existing_rect[i/3][j/3].find(next_value) != existing_rect[i/3][j/3].end()) continue;

                    existing_hor[i].insert(next_value);
                    existing_ver[j].insert(next_value);
                    existing_rect[i/3][j/3].insert(next_value);

                    map[i][j] = next_value;
                    if(backtracking(i, j)) 
                    {
                        return true;
                    }
                    map[i][j] = 0;

                    existing_hor[i].erase(next_value);
                    existing_ver[j].erase(next_value);
                    existing_rect[i/3][j/3].erase(next_value);
                }

                return false;
            }
            else if(i == 8 && j == 8) return true;
        }
    }
}

int main()
{
    for(int i = 0; i < 9; ++i)
    {
        for(int j = 0; j < 9; ++j)
        {
            cin >> map[i][j];

            if(map[i][j] == 0) 
            {
                for(int value = 1; value <= 9; ++value)
                {
                    possible[i][j].insert(value);
                }
                continue;
            }

            existing_hor[i].insert(map[i][j]);
            existing_ver[j].insert(map[i][j]);
            existing_rect[i/3][j/3].insert(map[i][j]);
        }
    }


    for(int i = 0; i < 9; ++i)
    {
        for(int j = 0; j < 9; ++j)
        {
            set<int>::iterator iter;
            for(iter = existing_hor[i].begin(); iter != existing_hor[i].end(); ++iter)
            {
                possible[i][j].erase(*iter);
            }

            for(iter = existing_ver[j].begin(); iter != existing_ver[j].end(); ++iter)
            {
                possible[i][j].erase(*iter);
            }

            for(iter = existing_rect[i/3][j/3].begin(); iter != existing_rect[i/3][j/3].end(); ++iter)
            {
                possible[i][j].erase(*iter);
            }
        }
    }

    backtracking();

    for(int i = 0; i < 9; ++i)
    {
        for(int j = 0; j < 9; ++j)
        {
            cout << map[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

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

문제

문제

출처

ICPC

백트래킹 시간복잡도 계산 질문입니다.

rlarlghks970113 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말