글 읽기 - 스도쿠 시간초과....

hiasince12 5년 전 0

제가 시간을 줄이고 줄였다고 생각했는데도 계속 시간초과가 나네요....

처음에는 3x3 박스를 체크하는 부분을 반복문으로 체크를 했는데, 상태를 저장하는 배열을 통해 1번에 체크하도록 했는데 시간초과가 나서

또 9x9를 돌면서 0의 자리를 체크했던 것을, 0의 자리를 저장하는 vector를 이용했습니다. 그런데도 시간 초과가 나네요 ㅠㅠ

어디서 더 줄일 수 있을 가요 ㅠㅠ

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

int map[9][9];
bool box[9][10];
vector<pair<int,int>> v;

bool is_promise(int x, int y, int v) {
    bool check = true;
    
    for(int i = 0 ; i < 9; i++) {
        if(map[x][i] == v)
            check = false;
        if(map[i][y] == v)
            check = false;
    }
    
    if(box[(x/3)*3+(y/3)][v])
        check = false;

    return check;
}

void backtracking() {
    if(v.empty()) {
        for(int i = 0 ; i < 9; i++) {
            for(int j = 0; j < 9 ; j++) {
                cout << map[i][j] << " ";
            }
            cout << endl;
        }
    }
    else {
        int x = v.back().first;
        int y = v.back().second;
        
        for(int i = 1; i <= 9 ; i++) {
            if(is_promise(x,y,i)) {
                map[x][y] = i;
                box[(x/3)*3 + (y/3)][i] = true;
                v.pop_back();
                backtracking();
                box[(x/3)*3 + (y/3)][i] = false;
                v.push_back({x,y});
                map[x][y] = 0;
            }
        }
    }
}

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) 
                box[(i/3)*3 + (j/3)][map[i][j]] = true;
            else
                v.push_back({i,j});
        }
    }
    
    backtracking();

    return 0;
}

djm03178 5년 전 0

"스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다."

hiasince12 5년 전 0

와... 플래그 추가하니까 해결댔네요 감사합니다.

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

문제

문제

출처

ICPC

스도쿠 시간초과....

hiasince12 5년 전 0

djm03178 5년 전 0

hiasince12 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말