[BOJ] 백준 2580 스도쿠

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

 Input 

0 3 5 4 6 9 2 7 8

7 8 2 1 0 5 6 0 9

0 6 0 2 7 8 1 3 5

3 2 1 0 4 6 8 9 7

8 0 4 9 1 3 5 0 6

5 9 6 8 2 0 4 1 3

9 1 7 6 5 2 0 8 0

6 0 3 7 0 1 9 5 2

2 5 8 3 9 4 7 6 0

 

 Output 

1 3 5 4 6 9 2 7 8

7 8 2 1 3 5 6 4 9

4 6 9 2 7 8 1 3 5

3 2 1 5 4 6 8 9 7

8 7 4 9 1 3 5 2 6

5 9 6 8 2 7 4 1 3

9 1 7 6 5 2 3 8 4

6 4 3 7 8 1 9 5 2

2 5 8 3 9 4 7 6 1

각 칸에서 확인해야 영역은 크게 3가지 입니다.

행row, 열col, 3×3 크기의 사각형

▷ row[a][b]: a번째 가로줄에 b라는 숫자 존재 여부

▷ col[a][b]: a번째 세로줄에 b라는 숫자 존재 여부

▷ square[a][b]: a번째 사각형에 b라는 숫자 존재 여부

비어있는 칸에 1~9까지 가능한 숫자를 모두 넣어보며 유효한지 확인합니다.

예를 들면, 아래 지점은 행row이든 열col이든 특정 숫자를 확실할 수 없기 때문에

가능한 후보를 모두 넣어보면서 최종적으로 모든 칸을 완성할 수 있는지 확인합니다. 

 

Q. 가능한 후보란?

행row: [6 2 7 8 1 3 5] → 4, 9

열col: [7 3 8 5 9 6 2] → 1, 4

3×3 사각형: [3 5 7 8 2 6] → 1, 4, 9

▶ 후보 = 1, 4, 9를 넣어서 모든 칸이 완성될 수 있는지 확인합니다.

    (스도쿠는 9 × 9 = 81칸을 가지고 있습니다.)

 

---

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력하기 위해

한 개를 찾은 후에는 exit(0);로 종료

#include <iostream>
using namespace std;
#define MAX 9
 
int map[MAX][MAX];
bool row[MAX][MAX], col[MAX][MAX], square[MAX][MAX];
 
void printAns(){
    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){
        printAns();
        exit(0);
    }
 
    if (map[x][y] == 0){
        for (int i = 1; i <= 9; i++){
            // 행, 열, 사각형 영역에 이미 존재하는 숫자인 경우
            if(row[x][i] || col[y][i] || square[(x / 3) * 3 + (y / 3)][i])
                continue;
        
            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);
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    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;
            }
        }
    }
 
    DFS(0);
}