[백준] 2580번 스도쿠

문제

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

풀이과정

스도쿠를 완성하는 문제이다. DFS와 백트래킹을 통해 가능한 수를 구해서 완성되면 출력한다.
스도쿠의 규칙은 열, 행 , 3x3 정사각형 칸에 1~9까지의 숫자가 한개씩만 존재해야한다.

이러한 규칙에 따라서 열, 행, 정사각형의 어떤 숫자(1~9)가 존재하는지 체크하는 배열을 만든다.

모든 경우의 수를 다 해볼 수 있지만 그렇게 하면 시간초과가 뜰 수 있다.

소스코드

#include <iostream>

using namespace std;

#define MAX_NUM 10

int sudoku_size = 9;
int sudoku[MAX_NUM][MAX_NUM];
bool chk_row[MAX_NUM][MAX_NUM]; // 행에 숫자(1~9)가 존재하는지 여부 확인
bool chk_col[MAX_NUM][MAX_NUM]; // 열에 숫자(1~9)가 존재하는지 여부 확인
bool chk_square[MAX_NUM][MAX_NUM]; // 정사각형(3x3)에 숫자(1~9)가 존재하는지 여부 확인


// (x,y)가 몇 번째 정사각형(0~8)에 해당하는지 return.
int square(int x, int y)
{
    return (x / 3) * 3 + (y / 3);
}

void print_Sudoku()
{
    for (int i = 0; i < sudoku_size; i++)
    {
        for (int j = 0; j < sudoku_size; j++)
        {
            cout << sudoku[i][j] << " ";
        }
        cout << "\n";
    }
}

void make_sudoku(int z)
{
    if (z == 81)
    {
        print_Sudoku();
        exit(0);
    }

    int x = z / sudoku_size, y = z % sudoku_size;

    if (sudoku[x][y] != 0)
    {
        make_sudoku(z + 1);
    }
    // 0이 들어가있는 곳이면
    else
    {
        // 들어갈 숫자 찾기
        for (int i = 1; i <= 9; i++)
        {
            // 해당 열, 행, 정사각형 안에 i가 없으면 i를 사용한다
            if (chk_row[x][i] == 0 && chk_col[y][i] == 0 && chk_square[square(x, y)][i] == 0)
            {
                chk_row[x][i] = chk_col[y][i] = chk_square[square(x, y)][i] = true;
                sudoku[x][y] = i;
                make_sudoku(z + 1);
                // 숫자 i가 아니면 백트래킹
                sudoku[x][y] = 0;
                chk_row[x][i] = chk_col[y][i] = chk_square[square(x, y)][i] = false;
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    for (int i = 0; i < sudoku_size; i++)
    {
        for (int j = 0; j < sudoku_size; j++)
        {
            cin >> sudoku[i][j];
            if (sudoku[i][j] != 0)
            {
                // 각 열, 행, 정사각형에 입력된 숫자가 있다고 저장한다.
                chk_row[i][sudoku[i][j]] = true;
                chk_col[j][sudoku[i][j]] = true;
                chk_square[square(i, j)][sudoku[i][j]] = true;
            }
        }
    }

    make_sudoku(0);

    return 0;
}