(C++) - 백준(BOJ) 2580번 : 스도쿠

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

2580번: 스도쿠

backtracking문제였습니다.

 

 

 

풀이방법

 1. 해당 행의 1 ~ 9사이의 수를 확인했다는 것을 나타내기 위해 2차원 배열들을 사용합니다. rowCk[i][num]은 i행의 num은 이미 확인되었다는 뜻입니다. 같은 방식으로 colCk[j][num]은 j열의 num을 확인했다는 뜻이고 squareCk[(i / 3) * 3 + (j / 3)][num]은 정사각형을 떼어 생각했을 때 몇 번째 칸의 num을 확인한 것인지를 나타냅니다.

 

 2. backtracking을 시행합니다.

최대 81칸을 확인할 수 있습니다. 이 확인하는 동작과 위치를 함수의 인자 cnt로 묶어 정의합니다. cnt / 9는 몇 번째 행인가를 나타내며 cnt % 9는 몇 번째 열인지를 나타냅니다. 

  2-1. 81번 확인했다면 답을 출력하고 프로그램을 종료합니다.

  2-2. 현재 칸이 0이라면 답을 찾아야합니다. 체크하지 않은 수를 넣고 전체적인 답이 맞는지 확인해줍니다. 0인칸에 임의의 수를 넣었으나 답이 아니라면 함수는 끝나고 넣었던 답과 체크했던 곳을 원복해줍니다.

 

 

Code

#include <bits/stdc++.h>
using namespace std;
int sudoku[10][10], rowCk[10][10], colCk[10][10], squareCk[100][10];
void backtracking(int cnt){
    int row = cnt / 9;
    int col = cnt % 9;
    
    if(cnt == 81) {
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                cout << sudoku[i][j] << ' ';
            }
            cout << '\n';
        }
        exit(0);
    }
    if(!sudoku[row][col]){
        for(int i = 1; i <= 9; i++){
            if(rowCk[row][i] || colCk[col][i] || squareCk[(row / 3) * 3 + (col / 3)][i]) continue;
            rowCk[row][i] = colCk[col][i] = squareCk[(row / 3) * 3 + (col / 3)][i] = 1;
            sudoku[row][col] = i;
            backtracking(cnt + 1);
            sudoku[row][col] = 0;
            rowCk[row][i] = colCk[col][i] = squareCk[(row / 3) * 3 + (col / 3)][i] = 0;
        }
    }
    else backtracking(cnt + 1);
}

int main(){
    for(int i = 0; i < 9; i++){
        for(int j = 0; j < 9; j++){
            cin >> sudoku[i][j];
            if(sudoku[i][j]){
                int num = sudoku[i][j];
                rowCk[i][num] = colCk[j][num] = squareCk[(i / 3) * 3 + (j / 3)][num] = 1;
            }
        }
    }
    backtracking(0);
}