백준, BOJ, 2580번, 스도쿠 : C++ [CPP] ★★

백트래킹에서 그래도 조건이 많이 붙어서 가지치기를 어떻게 하는지 공부할 만한 문제다.

행과 열 처리는 어떻게든 가능하지만

3*3이 어느 칸인지 찾는 것을 조금 고민해볼 필요는 있다.

결국 1~3까지 첫 째 4~6까지 두 번째.. 이렇게 생각하면 어떻게 할 지 감이 온다.

 

 

 

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

---

 

#맞은 풀이

#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);
}