[백준][2580번][DPS] 스도쿠

스도쿠

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

<문제>

<코드>

#include <iostream>
#include <stdio.h>
#include <cstdlib>
 
using namespace std;
 
int sudoku[9][9];
bool chk_row[9][9];
bool chk_col[9][9];
bool chk_square[9][9];
 
// 입력한 행,렬의 값이 어디 정사각형에 해당하는지
int square(int row, int col)
{
    return (row /3) *3 + (col/3);
}
 
void print_Sudoku()
{
    int i,j;
    for(i=0;i<9;i++)
    {
        for(j=0;j<9;j++)
        {
            printf("%d ",sudoku[i][j]);
        }
        printf("\n");
    }
}
 
void make_sudoku(int z)
{
    //탈출문
    if(z==81)
    {
        print_Sudoku();
        exit(0);
    }
    // 행 값, 열 값 설정
    int x = z / 9, y = z % 9;
 
    if(sudoku[x][y] != 0)
    {
        make_sudoku(z + 1);
    }
    else
    {
        // 숫자 하나씩 대입
        for(int i=1;i<=9;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);
                // 임의로 정한 스도쿠 값이 아니라면 백트래킹
                sudoku[x][y] = 0;
                chk_row[x][i] = chk_col[y][i] = chk_square[square(x,y)][i] = false;
            }
        }
    }
}
int main()
{
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            scanf("%d",&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);
}
 
 

<문제 푼 요령>

1. 스도쿠의 조건은 행, 열, 같은 사각형 내에 1~9의 숫자가 1개씩만 존재해야 한다는게 핵심이다.

2. 그것을 3개의 chk 형태로 된 2차원 배열로 만들어주고 dps 함수가 실행될 떄 3개의 chk 함수가 동시에 0이 될떄에만 백트래킹을 하게 해주면 된다.

3. 함수를 구현함에 있어서 해당 행과 열이 어느 사각형에 있는지 알려주기 위한 square 함수를 설정했다.