백준, BOJ, 2580번 C++ [CPP]

이 문제는 맞게 풀더라도

시간초과가 나는 문제다..

내가 시간초과가 어디서 났는지 잘보도록하자.

https://www.acmicpc.net/problem/2580

 

---

 

#1 시간초과 케이스

#include<iostream>
#include<vector>

using namespace std;

int pane[9][9]; // 9*9 게임판
bool check = false; // 답을 찾았는지 체크
vector<pair<int, int>> vec; // 채워야 할 곳의 좌표
int number = 0; // 채워야 할 곳의 개수



//조건 1.가로의 합 45, 2.세로의 합 45, 3.3*3 내의 합 45 를 이용해보자.(비효율적..)
// -> 하나의 행에 숫자가 중복되면 안됨, 하나의 열에... 하나의 3*3안에...
// 해당 위치의 값으로 조사
bool numCheck(int a, int b) {
    int target = pane[a][b]; // 비교할 숫자
    //같은 행에 숫자가 중복되어있나?
    for (int i = 0; i < 9; i++) {
        //자기 자신을 제외하고 행에서 중복이 된다?
        if (target == pane[a][i] && i != b) return false;
        //자기 자신을 제외하고 열에서 중복이 된다?
        if (target == pane[i][b] && i != a) return false;
    }
    //자신이 속한 3*3 정사각형 안에서 중복이 된다?
    int p = a / 3; // 어느 3*3 인지(행)
    int q = b / 3; // 어느 3*3 인지(렬)
    for (int i = p * 3; i < p * 3 + 3; i++) {
        for (int j = q * 3; j < q * 3 + 3; j++) {
            //자신을 제외한 값이 중복이 된다?
            if (target == pane[i][j] && i != a && j != b) return false;
        }
    }
    // 모든 조건이 성립하면 true
    return true;
}


// 0인 곳에 대해서 모두 선택해야함. 다 선택했을 시에 스도쿠의 조건에 맞나 확인하면 될듯.
void func(int cnt) {
    if (check) return; // 이미 결과가 있다면 바로 return
    //모두 선택했을 때
    if (cnt == number) {
        //조건,123을 다거치면 성립
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                cout << pane[i][j] << " ";
            }
            cout << "\n";
        }
        //여기까지 왔으면 성립하는 것이 있음.
        check = true;
        return;
    }
    
    //1~9까지 넣어봄
    for (int i = 1; i <= 9; i++) {
        //선택
        auto a = vec.back();
        vec.pop_back();
        int col = a.first;
        int row = a.second;

        //구현
        pane[col][row] = i;

        //여기서 숫자를 넣었을 때 checkNum()을 실행해서 넣을 수 있는 숫자인지 확인.
        if (numCheck(col, row)) {
            //넣을 수 있는 숫자면 넣음.
            func(cnt + 1);
        }

        //복원
        vec.push_back(a);
        pane[col][row] = 0;
    }
    return;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    //입력받음
    for (int x = 0; x < 9; x++) {
        for (int y = 0; y < 9; y++) {
            cin >> pane[x][y];
            if (pane[x][y] == 0) {
                vec.push_back({ x,y });
                number++;
            }
        }
    }
    func(0);
}

 

여기서 vec에서 값을 할당하는 문제가 생겼다..

func()에서

for문 돌릴 때

이 부분에서 vec 접근을 index로 하면 시간초과가 안뜨고 성공한다.

#include<iostream>
#include<vector>
using namespace std;
int pane[9][9]; // 9*9 게임판
bool check = false; // 답을 찾았는지 체크
vector<pair<int, int>> vec; // 채워야 할 곳의 좌표
int number = 0; // 채워야 할 곳의 개수
//조건 1.가로의 합 45, 2.세로의 합 45, 3.3*3 내의 합 45 를 이용해보자.(비효율적..)
// -> 하나의 행에 숫자가 중복되면 안됨, 하나의 열에... 하나의 3*3안에...
// 해당 위치의 값으로 조사
bool numCheck(int a, int b) {
    int target = pane[a][b]; // 비교할 숫자
    //같은 행에 숫자가 중복되어있나?
    for (int i = 0; i < 9; i++) {
        //자기 자신을 제외하고 행에서 중복이 된다?
        if (target == pane[a][i] && i != b) return false;
        //자기 자신을 제외하고 열에서 중복이 된다?
        if (target == pane[i][b] && i != a) return false;
    }
    //자신이 속한 3*3 정사각형 안에서 중복이 된다?
    int p = a / 3; // 어느 3*3 인지(행)
    int q = b / 3; // 어느 3*3 인지(렬)
    for (int i = p * 3; i < p * 3 + 3; i++) {
        for (int j = q * 3; j < q * 3 + 3; j++) {
            //자신을 제외한 값이 중복이 된다?
            if (target == pane[i][j] && i != a && j != b) return false;
        }
    }
    // 모든 조건이 성립하면 true
    return true;
}
// 0인 곳에 대해서 모두 선택해야함. 다 선택했을 시에 스도쿠의 조건에 맞나 확인하면 될듯.
void func(int cnt) {
    if (check) return; // 이미 결과가 있다면 바로 return
    //모두 선택했을 때
    if (cnt == number) {
        //조건,123을 다거치면 성립
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                cout << pane[i][j] << " ";
            }
            cout << "\n";
        }
        //여기까지 왔으면 성립하는 것이 있음.
        check = true;
        return;
    }

    //1~9까지 넣어봄
    for (int i = 1; i <= 9; i++) {
        //선택
        auto a = vec[cnt];
        int col = a.first;
        int row = a.second;
        //구현
        pane[col][row] = i;
        //여기서 숫자를 넣었을 때 checkNum()을 실행해서 넣을 수 있는 숫자인지 확인.
        if (numCheck(col, row)) {
            //넣을 수 있는 숫자면 넣음.
            func(cnt + 1);
        }
        //복원
        pane[col][row] = 0;
    }
    return;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    //입력받음
    for (int x = 0; x < 9; x++) {
        for (int y = 0; y < 9; y++) {
            cin >> pane[x][y];
            if (pane[x][y] == 0) {
                vec.push_back({ x,y });
                number++;
            }
        }
    }
    func(0);
}

 

 

여기서 중요한 점은

백트래킹을 하더라도

 

1~9까지 다 넣을 것인지?

아니면 걸러서 넣을 것인지?

즉, 여기서 numCheck()가 시간을 줄이는데 한몫을 한 것이다.

 

다시 말해서 백트래킹 시간초과의 핵심은

for문 반복문의 연속이 되고 싶지 않다면

넣을 때 필요한 조건을 집어넣어야 한다는 것이다.