#2580번 스도쿠 (c++)

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

2580번: 스도쿠

스토쿠(9x9)에서 숫자를 집어 넣는데는 조건이 있다. 

1. 가로

2. 세로

3. 3x3칸

이 세 가지에서 겹치는 숫자가 없어야 숫자를 넣을 수 있다. 

따라서 재귀함수로 이 세 가지를 판별하기로 했다.

 

배열은 먼저 int형식으로 만들었고, bool문으로 각 조건들을 판단하며, 상기 언급된 판별문들은 매크로함수를 이용하여 설정했다.

다만, 백트래킹의 원리를 아직 이해못한 탓에 문제를 푸는데 번번히 실수했다. 

아직 백트래킹의 재귀원리를 이해하지 못해서였다.

 

결국 다른 사람의 풀이를 보며 알음알음 이해했다.

https://yabmoons.tistory.com/88

[ 백준 2580 ] 스도쿠 (C++)

#include <iostream>
#define MAX 9
using namespace std;

int Map[MAX][MAX];
bool Row[MAX][MAX];
bool Col[MAX][MAX];
bool Square[MAX][MAX];

void Input(){
    for(int i=0; i<MAX; i++){
        for(int j=0; j<MAX; j++){
            cin >> Map[i][j];
            if(Map[i][j]!=0){
                Row[i][Map[i][j]] = true;
                Col[j][Map[i][j]] = true;
                Square[(i/3)*3 + (j/3)][Map[i][j]] = true;
            }
        }
    }
}

void Print(){
    for(int i=0; i<MAX; i++){
        for(int j=0; j<MAX; j++){
            cout << Map[i][j] << " ";
        }
        cout << "\n";
    }
}

void DFS(int Cnt){
    int x = Cnt/MAX;
    int y = Cnt%MAX;
    
    if(Cnt==81){
        Print();
        exit(0);
    }
    
    if(Map[x][y]==0){
        for(int i=1; i<=9; i++){
            if(Row[x][i]==false&&Col[y][i]==false&&Square[(x/3)*3+(y/3)][i]==false){
                Row[x][i] = true;
                Col[y][i] = true;
                Square[(x/3)*3 +(y/3)][i] = true;
                Map[x][y] = i;
                DFS(Cnt+1); // 해당 숫자가 아닐 경우 백트래킹 시작
                Map[x][y] = 0;
                Row[x][i] = false;
                Col[y][i] = false;
                Square[(x/3)*3+(y/3)][i] = false;
            }
        }
    }
    else DFS(Cnt+1);
}

void Solution(){
    DFS(0);
}

void Solve(){
    Input();
    Solution();
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    Solve();
    
    return 0;
}