[백트래킹] 스도쿠 (백준 2580번)

알고리즘 구분

 

알고리즘을 공부하며 가장 헷갈린 것이, 알고리즘의 이름이 무얼 의미하는지 몰랐던 부분이었다.

n-Queen 문제를 풀 때도, 풀이를 보고 신기했던 경험이 있었지만 백트래킹에 대한 이해는 얕았다.

그러나 그것이 스도쿠 문제를 풀면서 완전한 이해로 갖춰지게 된 거 같다.

 

일단 기본적으로, 브루트 포스가 있다.

브루트 포스는 for문이든 중첩된 for문이든 간에 모든 경우의 수를 다 찾아보는 방식이다.

이 브루트 포스에서 방문한 칸을 체크하는 것으로 효율을 꾀하는 것이 dfs와 bfs로 나타난다.

 

그러나 dfs는 갈래의 마지막까지 방문한 다음에 옳고 그름을 판단하는데, 다음의 문제가 있다

1) 만약 재귀가 끝나지 않는다면? -> 런 타임 에러가 발생한다.

2) 중간에 틀린 걸 판별했다면? -> 중간에 멈추지 않기 때문에 비효율적이다.

 

이것을 해결하기 위해서 고안된 방식이 바로 백트래킹이다.

밑에 작성한 코드를 보면 알 수 있겠지만, 백트래킹은 매개변수로 현재 재귀 위치를 받는다.

n-Queen 문제에서는 y축을 위에서부터 아래로 훑기 때문에 y축 위치를 매개 변수로 받았고

스도쿠 문제에서는 총 81칸을 훑을 거기 때문에 해결이 된 칸의 개수를 매개 변수로 받았다.

 

만약 스도쿠 문제의 임의의 재귀 구간, 예를 들어서 41번째 칸이 틀렸다는 게 밝혀지면,

41번째 칸부터 다시 재귀를 시작하기 때문에 1번 칸으로 돌아갈 필요가 없다.

 

bfs는 dfs처럼 재귀를 타지 않기 때문에 2가지 문제점이 발생하지 않지만,

그럼에도 이것에 가중치를 더해서 만든 다익스트라 알고리즘으로 분화된다.

 

브루트 포스, dfs, 백트래킹, bfs, 다익스트라 이렇게 5가지에 대한 설명이었다.

 

- - -

 

설명은 이 정도면 됐으니 스도쿠 문제의 코드를 올린다.

 

 

#include <iostream>
using namespace std;
 
#define MAX 9
 
int sudoku[MAX][MAX];
 
bool col[MAX][MAX+1];
bool row[MAX][MAX+1];
bool square[MAX][MAX+1];
 
// col의 첫번째 매개변수에는 x축을, 두번째 매개변수에는 1부터 9까지의 숫자가 들어간다.
// row의 첫번째 매개변수에는 y축을, 두번째 매개변수에는 1부터 9까지의 숫자가 들어간다.
// square의 첫번째 매개변수는 3*3 크기를 하나로 묶어 일종의 1차원 배열처럼 0,1,2,3,4,5,6,7,8로 변환한 값을 넣는다.
// square의 두번째 매개변수에는 1부터 9까지의 숫자가 들어간다.
 
// 이 bool형 배열들은 해당하는 자연수가 이미 있는지 없는지를 따지기 위해 만들어졌다.
 
int convertSquare(int y, int x)
{
    return (y / 3) * 3 + x / 3;
}
// 위에서 말한 square 배열의 첫번째 인자를 결정하는 함수이다.
// y축의 값을 3으로 나눈 후 다시 3을 곱해준 값에 x축 값을 3으로 나눈 값을 더해주면 아래의 꼴로 나온다.
 
/*
0 1 2
3 4 5
6 7 8
여기서 각각의 숫자들은 3*3 크기의 정사각형을 의미한다.
*/
 
void dfs(int cnt)
{
    if (cnt == 81)
    {
        for (int i = 0; i < MAX; i++)
        {
            for (int j = 0; j < MAX; j++)
            {
                cout << sudoku[i][j] << ' ';
            }
            cout << endl;
        }
        exit(0);
    }
    // 위의 조건문은 탐색이 끝나는 조건을 의미한다.
    // cnt는 숫자가 채워진 칸의 개수를 의미하는데 이게 81(MAX * MAX)인 시점에 끝난다.
 
    int y = cnt / MAX;
    int x = cnt % MAX;
    // cnt는 1씩 증가하기 때문에 0,0부터 8,8까지의 모든 칸을 탐색할 수 있다.
 
    if (sudoku[y][x])
        dfs(cnt + 1);
    // 칸이 채워져 있으면 다음 칸으로 간다. (++cnt 자체가 다음 칸으로 간다는 뜻이다.)
    else
    // 칸이 채워져 있지 않다면, 아래의 for문을 실행한다.
    {
        for (int i = 1; i <= MAX; i++)
        // 이 반복문은 1부터 9까지의 숫자를 대입해보기 위해 만들어졌다.
        {
            
            if (!col[x][i] && !row[y][i] && !square[convertSquare(y,x)][i])
            // 만약 해당하는 숫자가 아직 없다면,
            // 값을 대입해보고, col,row,square 배열도 true로 모두 바꿔서 대입했음을 나타낸다.
            {
            sudoku[y][x] = i;
            col[x][i] = true;
            row[y][i] = true;
            square[convertSquare(y, x)][i] = true;
            dfs(cnt + 1);
            // 대입이 끝났으면 다음 칸으로 진행을 하는데, 문제가 없다면 계속 cnt는 늘어날 것이고
            // 만약 문제가 발생한다면 (중복이 발생한다면) 재귀가 하나씩 풀리며 문제 발생 전으로 온다.
 
            sudoku[y][x] = 0;
            col[x][i] = false;
            row[y][i] = false;
            square[convertSquare(y, x)][i] = false;
            // 만약 문제가 발생했다면 그 칸은 다시 모든 대입을 풀어주기 때문에 위의 4줄을 진행한다.
            }
        }
    }
}
 
int main(void)
{
    for (int i = 0; i < MAX; i++)
        for (int j = 0; j < MAX; j++)
        {
            cin >> sudoku[i][j];
            // 대입을 해주고,
            if (sudoku[i][j])
            {
                // 대입된 경우에는 해당 숫자가 대입되었음을 true값으로 표시해준다.
                col[j][sudoku[i][j]] = true;
                row[i][sudoku[i][j]] = true;
                square[convertSquare(i, j)][sudoku[i][j]] = true;
            }
        }
 
    dfs(0);
    // 매개변수인 cnt에 대한 설명은 dfs 내부에 설명되어 있다.
    // dfs(0)부터 dfs(81)까지 진행될 것이다.
}