[백준] 2580 스도쿠, C++

2580번: 스도쿠

문제 요약

스도쿠 정답을 찾으면된다.
행과 열, 3X3 안에 1~9가 중복없이 들어가야한다.

 

접근

1. Brute-force

숫자를 넣어야하는 자리수는 최대 81개이고 1부터 9까지 모든 값을 넣어서 확인하려면 9⁸¹ 이 된다.
O(2³²) 는 대충 42초 정도 걸리는데 이 값보다 크므로 이 방법으로 풀수 없다.
물론 0인 위치에서만 확인하면 되지만 찾아야하는 위치가 9개 이상이면 3초가 넘으므로 입력값을 알지 못하면 풀수 없다.

2. Backtracking

백트래킹으로 조건이 맞지 않은 경우는 가지치기를 통해 탐색하는 개수를 줄이면된다.

 

알고리즘

1. (1,1)부터 (9,9) 까지 모든 점을 순회한다.
2. 값이 0인 위치에서 1부터 9까지 모든 점을 넣고 재귀함수를 불러온다.
3. 순회 도중에 조건이 위배되는 경우는 return으로 돌아간다.
4. 마지막 위치에 도달한경우 배열을 출력하고 프로그램을 종료시킨다.

 

새로 알게된 것

없음

 

전체 코드

#include <iostream>
#include <vector>

using namespace std;

int sudoku[9][9];

void printSudoku()
{
    for (int r=0;r<9;r++)
        for (int c=0;c<9;c++)
            cout << sudoku[r][c] << " ";
        cout << endl;
}

int checkSudoku(int r, int c, int val)
{
    int sdk[10] = { 0, };
    // 1 row
    for (int cc=0; cc<9; cc++)
        if (sudoku[r][cc] == val) 
            return false;
    // 2 column
    for (int rr=0; rr<9; rr++)
        if (sudoku[rr][c] == val) 
            return false;
    // 3 3*3 square
    for (int rr=0; rr<3; rr++)
        for (int cc=0; cc<3; cc++)
            if (sudoku[(r/3)*3 + rr][(c/3)*3 + cc] == val)
                return false;
    // skip all return true
    return true;
}

void backtrack(int index)
{
    if (index == 81)
    {
        printSudoku();
        exit(0); // program exit
    }
    if (sudoku[index/9][index%9] != 0) // if number is fixed, go next
    {
        backtrack(index+1);
        return;
    }
    for (int i=1; i<=9; i++) // if number is zero, find number
    {
        if (!checkSudoku(index/9, index%9, i)) continue; // check conditions
        sudoku[index/9][index%9] = i;
        backtrack(index+1);
        sudoku[index/9][index%9] = 0;
    }
}

int main()
{
    for (int i=0;i<81;i++) cin >> sudoku[i/9][i%9];
    backtrack(0);
    return 0;
}