[백준 2580번] 스도쿠

풀이

---

백트래킹이란 모든 경우의수를 모두 탐색하는 것을 뜻한다.

스도쿠에서도 모든 경우의수를 1~9까지 다돌릴수있지만 다돌리게 되면 시간초과가 뜰수도 있다.

그래서 확인해야할 번호만 체크해서 돌려보는게 이문제의 포인트이다.

가로를 체크하는 배열, 세로를 체크하는 배열, 영역을 체크하는 배열 총3개를 만들어서 1~9까지 확인해보고 없는 숫자를 체크해두었다가 하나씩 넣어보면 된다.

소스코드

---

#include <iostream>
using namespace std;
 
int map[10][10];
int zero_point[2][101],zero_add=0; // 0 의 위치를 저장하는 변수
int garo[10][10] = { 0, }, sero[10][10] = { 0, }, nine[10][10] = { 0, }; // 가로, 세로, 구역별 checking 배열
int flag = 0;
 
void sdk(int zero) {
    if (flag) return;
    if (zero == zero_add) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                cout << map[i][j] << " ";
            }
            cout << '\n';
        }
        flag = 1;
        return;
    }
 
    int x = zero_point[0][zero];  // 세로
    int y = zero_point[1][zero];  // 가로
    int num[10] = { 0, };
 
    for (int i = 1; i < 10; i++) {
        num[i] = 1;
        if (garo[x][i]) num[i] = 0;
        else if (sero[y][i]) num[i] = 0;
        else if (nine[(x / 3) * 3 + (y / 3)][i]) num[i] = 0;
 
        if (num[i]) num[0]++;
    }
 
    if (!num[0]) return;
 
    //들어갈 수 있는 숫자 탐색
    for (int i = 1; i <= 9; i++) {
        if (num[i]) {
            map[x][y] = i;
            garo[x][i] = sero[y][i] = nine[(x/3)*3+(y/3)][i] = 1;
            sdk(zero + 1);
            map[x][y] = 0;
            garo[x][i] = sero[y][i] = nine[(x / 3) * 3 + (y / 3)][i] = 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인 부분 주소값 저장 (최대 100개)
                zero_point[0][zero_add] = i; // 세로
                zero_point[1][zero_add] = j; // 가로
                zero_add++;
            }
            else {  // 숫자라면 체크
                garo[i][map[i][j]] = 1;  // 가로는 위에서부터 0번지
                sero[j][map[i][j]] = 1;  // 세로는 왼쪽에서부터 0번지
                nine[(i/3)*3+(j/3)][map[i][j]] = 1; // 구역은 왼쪽 위부터 0번지
            }
        }
    }
    // 연산부
    sdk(0);
 
    //출력부
    
    return 0;
}