[C/C++] 백준 #2239 스도쿠(백트래킹)

#2239 스도쿠 문제는 고전적인 백트래킹을 사용해서 푸는 문제입니다.

 

문제의 링크입니다.

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

2239번: 스도쿠

 

스도쿠는 가로와 세로가 각각 9칸을 가지고 있는 숫자 퍼즐입니다.

스도쿠의 숫자는 법칙이 있는데, 각각의 가로줄에 1부터 9까지의 숫자가 오직 한번씩만 사용되어야 하고, 각각의 세로줄에도 같은 법칙이 성립합니다.  그리고 3x3 짜리 작은 정사각형 안에도 1부터 9까지의 숫자가 오직 한번씩만 사용되어야 합니다.

 

백트래킹이 복잡한 알고리즘은 아니고, 깊이 우선 탐색을 사용한 방법입니다.  단지, 중간에 답으로서 가치가 없다면, 더 이상의 탐색을 그만두고 이전으로 돌아가는 것입니다.  저는 이문제의 조건을 보다 간편하게 검사하기 위해서 총 27개의 비트 플래그를 사용하였습니다.  가로줄 9개, 세로줄 9개, 그리고 3x3짜리 작은 정사각형 9개입니다.  1부터 9까지의 숫자가 오직 한번씩만 사용해야 하기 때문에 비트 플래그로 쉽게 작업을 할 수 있습니다.

 

이와 같이 비트 플래그를 이용하는 방법은 프로그램 자체를 보다 쉽게 작성할 수 있게 합니다.  안 그러면, 일일이 찾아가봐야 하는 복잡성이 남아있게 됩니다.

 

이 부분이 비트 플래그를 이용해서 해당 위치에 숫자가 들어가는 것이 맞는지 검사하는 부분입니다.  들어갈 위치는 왼쪽 위부터 0부터 시작해서 오른쪽 아래가 80이 되도록 차례대로 부여했습니다.  그러면 n에 따라서 어느 작은 박스에 들어갈 것인지는 n/27로 나누게 되면 위에서부터 3줄이 총 27개이므로, 어느 작은 정사각형인지 알 수 있습니다.  가로쪽은 가로쪽 열을 찾아내서 3으로 나누어 처리했습니다.

        if(small[n/27][(n%9)/3] & (1<<i)) continue;
        if(row[n/9] & (1<<i)) continue;
        if(col[n%9] & (1<<i)) continue;

 

그래서 작성된 소스는 다음과 같습니다.

//------------------------------------------------
//    baekjoon #2239 - Sudoku
//        - by Aubrey Choi
//        - created at 2019-08-19
//------------------------------------------------
#include <stdio.h>

char sudoku[81];
int small[3][3], row[9], col[9];
bool solve(int n)
{
    for(;sudoku[n] && n < 81;n++);
    if(n==81) return true;
    for(int i=1;i<=9;i++)
    {
        if(small[n/27][(n%9)/3] & (1<<i)) continue;
        if(row[n/9] & (1<<i)) continue;
        if(col[n%9] & (1<<i)) continue;
        small[n/27][(n%9)/3] |= (1<<i);
        row[n/9] |= (1<<i); col[n%9] |= (1<<i);
        sudoku[n]=i;
        if(solve(n+1)) return true;
        small[n/27][(n%9)/3] &= ~(1<<i);
        row[n/9] &= ~(1<<i); col[n%9] &= ~(1<<i);
    }
    sudoku[n]=0;
    return false;
}
int main()
{
    int i, j;
    for(i=0; i<9; i++)
    {
        char line[12];
        fgets(line,12,stdin);
        for(j=0; j<9; j++)
        {
            int s = i*9+j;
            sudoku[s]=line[j]-'0';
            if(!sudoku[s]) continue;
            int mask = 1<<sudoku[s];
            small[i/3][j/3] |= mask;
            row[i] |= mask;
            col[j] |= mask;
        }
    }
    solve(0);
    for(i=0;i<9;i++){for(j=0;j<9;j++)putchar(sudoku[i*9+j]+'0');putchar('\n');}
}