[algorithm] 백준 - 스도쿠

이 문제는 brute force 문제이다.

 

스도쿠 문제를 풀어봤다면 규칙을 정확히 알고 있을 것이다.

 

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

 

2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

 

dfs로 풀었다.

 

1. 숫자를 입력받을 때 가로줄, 세로줄, 3x3 정사각형에 쓰여진 숫자에 대한 기록을 한다.

 

3x3 정사각형을 위와 같이 나누고 숫자 각각에 대한 기록을 하기 위해서는

 

sudoku[y][x] 라고 가정했을 때,

 

y / 3 * 3 + x / 3 이라는 식을 통해 정사각형을 나눌 수 있다.

 

sudoku[1][1]일 경우

1 / 3 * 3 + 1 / 3 = 0 * 3 + 0 = 0

sudoku[2][3]일 경우

2 / 3 * 3 + 3 / 3 = 0 * 3 + 1 = 1

 

가로줄은 row, 세로줄은 column, 3 * 3 정사각형은 square로 배열 변수를 설정하여

 

숫자의 유무를 설정한다.

 

for(int i = 0; i < 9; i ++){
        for(int j = 0; j < 9; j++){
            cin >> sudoku[i][j];
            if(sudoku[i][j] != 0){
                row[i][sudoku[i][j]] = true;
                column[j][sudoku[i][j]] = true;
                square[(i/3)*3 + j/3][sudoku[i][j]] = true;
            }
        }
    }

 

2. count에 따라 x와 y를 구하고,

 

만일 x, y에 위치한 숫자가 0일 경우,

 

1부터 9 까지 반복문을 돌렸을 때, row, column, square 에 존재하지 않는 수를 배열에 넣어준다.

 

그리고 각 배열에 그 수가 있음을 표시한다.

 

재귀가 끝난 후, 다시 새로운 수에 대한 가지치기를 하기위해

 

row, column, square에 그 수가 없다고 표시한 후 다시 반복문을 돌게끔 한다.

 

 만일 숫자가 0이 아닐 경우,

 

다른 인덱스를 방문하기 위해 재귀함수를 호출한다.

 

    int y = count / 9;
    int x = count % 9;
    if(sudoku[y][x] == 0){
        for(int i = 1; i <= 9; i++){
            if(!row[y][i]&& !column[x][i] && !square[(y/3)*3 + x/3][i]){
                sudoku[y][x] = i;
                row[y][i] = true;
                column[x][i] = true;
                square[(y/3)*3 + x/3][i] = true;
                dfs(count + 1);
                sudoku[y][x] = 0;
                row[y][i] = false;
                column[x][i] = false;
                square[(y/3)*3 + x/3][i] = false;
            }
        }
    }
    else{
        dfs(count + 1);
    }
    
}

 

재귀를 돌다가 count가 81이 되면, print를 하고,

 

다른 경우의 수를 print하지 않고 재귀를 완전히 나가기 위해

 

exit(0)을 호출한다.

 

if(count == 81){
    for(int i = 0; i < 9; i ++){
        for(int j = 0; j < 9; j++){
            cout << sudoku[i][j] << " ";
        }
        cout << "\n";
    }
        exit(0);
    }

 

전체적인 코드는 이와 같다.

//스도쿠
#include <iostream>
using namespace std;

int sudoku[10][10];
bool row[10][10];
bool column[10][10];
bool square[10][10];
void dfs(int count){
    if(count == 81){
    for(int i = 0; i < 9; i ++){
        for(int j = 0; j < 9; j++){
            cout << sudoku[i][j] << " ";
        }
        cout << "\n";
    }
        exit(0);
    }
    int y = count / 9;
    int x = count % 9;
    if(sudoku[y][x] == 0){
        for(int i = 1; i <= 9; i++){
            if(!row[y][i]&& !column[x][i] && !square[(y/3)*3 + x/3][i]){
                sudoku[y][x] = i;
                row[y][i] = true;
                column[x][i] = true;
                square[(y/3)*3 + x/3][i] = true;
                dfs(count + 1);
                sudoku[y][x] = 0;
                row[y][i] = false;
                column[x][i] = false;
                square[(y/3)*3 + x/3][i] = false;
            }
        }
    }
    else{
        dfs(count + 1);
    }
    
}
int main(void){
    for(int i = 0; i < 9; i ++){
        for(int j = 0; j < 9; j++){
            cin >> sudoku[i][j];
            if(sudoku[i][j] != 0){
                row[i][sudoku[i][j]] = true;
                column[j][sudoku[i][j]] = true;
                square[(i/3)*3 + j/3][sudoku[i][j]] = true;
            }
        }
    }
    dfs(0);
}