글 읽기 - 스도쿠 문제, 시간을 줄일 수 있는 부분이 궁금합니다.

cys9872 3년 전 0

빈 칸만 재귀하며 비교하는데

90%정도에서 시간초과됩니다.

빈 칸의 넣을 수 있는 수를 찾는 함수도 시간을 줄여보고

별 짓을 다 하고

입출력 가속 또한 시도했지만 오히려 느려지는데

코드에서 시간초과를 유발하는 부분이 어디일까요

//#include "Algorithm Header.h"
#include "bits/stdc++.h"
using namespace std;

void sol(vector<vector<int>> board, vector<pair<int,int>> pos);
vector<int> findCandidate(vector<int> board);

bool flag = false;

int main(int argc, const char * argv[])
{
    //freopen("input.txt", "r", stdin);
    
    vector<vector<int>> board(9, vector<int> (9));
    vector<pair<int,int>> pos;
    
    for (int i=0; i<9; i++) {
        for(int j=0; j<9; j++){
            int n;
            scanf("%d", &n);
            board[i][j] = n;
            if (n == 0) pos.push_back({i, j});
        }
    }
    
    sol(board, pos);
    
    return 0;

}

vector<int> findCandidate(vector<vector<int>> board, int y, int x)
{
    vector<int> candidate(10);
    //가로와 세로에 있는 수를 카운트
    for(int i=0; i<9; i++)
    {
        candidate[ board[y][i] ] += 1;
        candidate[ board[i][x] ] += 1;
    }
    //
    
    //큰 칸의 수를 카운트
    int X = x - (x % 3);
    int Y = y - (y % 3);
    
    for (int i=0; i<3; i++)
    {
        for (int j=0; j<3; j++)
        {
           candidate[ board[Y+i][X+j] ] += 1;
        }
    }
    //
    
    vector<int> rt;
    for(int i=1; i<10; i++) if(candidate[i] == 0) rt.push_back(i);
    return rt;
}

void sol(vector<vector<int>> board, vector<pair<int,int>> pos)
{
    if(flag) return;
    
    if(pos.empty())
    {
        for (int i=0; i<9; i++) {
            for (int j=0; j<9; j++) {
                printf("%d ", board[i][j]);
            }
            printf("\n");
        }
        printf("\n");
        flag = true;
        return;
    }
    
    int y = pos.begin()->first;
    int x = pos.begin()->second;
    pos.erase(pos.begin());
    
    vector<int> candidiates = findCandidate(board, y, x);
    
    if(candidiates.empty()) return;
    for(int i : candidiates)
    {
        board[y][x] = i;
        sol(board, pos);
        if(flag) return;
    }
}

cys9872 3년 전 0

함수에 인자를 사용하는 것과 전역변수를 사용하는 것이

메모리 뿐만이 아니라 시간에도 영향을 주는 줄 몰랐습니다.

스도쿠 보드를 전역변수로 사용하여 해결하였습니다.

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

문제

문제

출처

ICPC

스도쿠 문제, 시간을 줄일 수 있는 부분이 궁금합니다.

cys9872 3년 전 0

cys9872 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말