글 읽기 - 시간초과가 나는 코드 함께 봐주실 분 계십니까

cntod2678 6년 전 0

시간초과가 계속 나는데 어디서 줄여야 할지 잘 안잡힙니다. 혹시 함께 봐주실 분 계시면 감사하겠습니다.

#include <iostream>
#include <vector>
using namespace std;

int arr[10][10];
vector<pair<int, int> > vii;
int endFlag = false;
int idx = 0;
int size = 0;

bool chkZero() {
    for(int i = 1; i <= 9; i++) {
        for(int j = 1; j <= 9; j++) {
            if(arr[i][j] == 0) return false;
        }
    }
    return true;
}

void print() {
    for(int i = 1; i <= 9; i++) {
        for(int j = 1; j <= 9; j++) {
            cout << arr[i][j] << " ";
        }
        cout << "\n";
    }
}

bool promising(int y, int x, int num) {
    int cntX, cntY;
    cntX = cntY = 0;
    for(int i = 1; i <= 9; i++) {
        if(arr[i][x] == num) cntY++;
        if(arr[y][i] == num) cntX++;
        
        if(cntX >= 2 || cntY >= 2) return false;
    }
    
    int cntG = 0;
    int gx, gy;
    gx = ((x-1) / 3) * 3;
    gy = ((y-1) / 3) * 3;
    for(int i = gx+1; i <= gx+3; i++) {
        for(int j = gy+1; j <= gy+3; j++) {
            if(arr[i][j] == num) cntG++;
        }
    }
    
    if(cntG >= 2)
        return false;
    
    return true;
}

void solve(int y, int x) {
    if(endFlag)
        return;
    
    int num = 1;
    while(num <= 9) {
        arr[y][x] = num;
        if(promising(y, x, num)) {
            if(chkZero()) {
                endFlag = true;
                print();
                return;
            } else {
                idx++;
                if(idx < vii.size())
                    solve(vii[idx].first, vii[idx].second);
            }
        } else {
            arr[y][x] = 0;
            num++;
        }
        if(endFlag)
            return;
    }
}


int main() {
    for(int i = 1; i <= 9; i++) {
        for(int j = 1; j <= 9; j++) {
            cin >> arr[i][j];
            if(arr[i][j] == 0) {
                vii.push_back(make_pair(i, j));
                size++;
            }
        }
    }
    
    idx = 0;
    solve(vii[0].first, vii[0].second);
    
    return 0;
}

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

문제

문제

출처

ICPC

시간초과가 나는 코드 함께 봐주실 분 계십니까

cntod2678 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말