[ 백준 2580 ] 스도쿠 (C++)

백준의 스도쿠(2580) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 이 문제는 스도쿠 게임의 빈칸에 알맞은 숫자를 채워넣어야 하는 문제이다.

   스도쿠 게임은 총 9x9 판위에서 이루어지며, 가로 9칸씩 9줄, 세로 9칸씩 9줄, 3x3크기의 정사각형 9칸씩 안에

   1~9의 숫자가 겹치지 않게 들어가게 만드는 게임이다.

   입력으로 주어지는 빈칸을 채워넣어야 하며, 빈칸에 들어갈 만한 숫자들만 적절한 가치지기를 통해서 선발한 후,

   그 숫자들을 실제로 넣어보고, 성립이 되는지 안되는지 판별해보고, 안된다면 다른 숫자들을 넣는 방식의 백트래킹을

   이용해서 문제를 해결할 수 있다.

2) 먼저 본인은 3개의 2차원배열을 사용하였다.

   Row[][], Col[][], Square[][] 이렇게 총 3개의 2차원 배열을 사용하였다.

   각각의 의미는 Row = 가로, Col = 세로, Square = 사각형을 의미하며,

   Row[a][b] = true 의 의미는 " a번째 가로줄에 b라는 숫자는 이미 존재합니다. "

   Col[a][b] = true 의 의미는 " a번째 세로줄에 b라는 숫자는 이미 존재합니다."

   Square[a][b] = true 의 의미는 "a번째 사각형에 b라는 숫자는 이미 존재합니다."

   이러한 의미들을 갖는다. false라면 그 해당 값이 존재하지 않는다는 의미이다.

   따라서, 입력받을 때 0이 아닌 숫자를 입력받는다면 바로바로 위의 배열들에 표시를 해주었다.

   그런데, Square[][] 에는 어떻게 표시를 할까?? 9x9에서 사각형의 번호를 어떻게 알아내야할까??

  

   위의 전체 맵에서 3x3씩 나눠본다면, 위의 그림처럼 0~3번의 번호를 갖는 3x3 사각형 9개가 만들어진다.

   그렇다면 (0, 0) = 0번, (0, 3) = 1번 등등... 각 좌표들이 몇 번 사각형에 속하는지 구하는 법에 대해 알아보자.

   식부터 설명하자면 (x좌표 / 3) * 3 + (y좌표 / 3) 이 된다.

   (0, 1) 같은 경우 0번 사각형에 속하고 위의 공식에 대입해보면, (0 / 3) * 3 + ( 1 / 3) = 0 + 0 = 0 으로 0번 사각형에

   속함을 확인할 수 있다. 이런 공식을 통해서 몇번 사각형에 들어가는지도 확인할 수 있다.

   즉, 우리는 입력받을 때 0이 아닌 숫자들에 대해서 이 모든 값들을 체크해줘야 한다. 

for (int i = 0; i < MAX; i++)
{
    for (int j = 0; j < MAX; j++)
    {
        cin >> MAP[i][j];
        if (MAP[i][j] != 0)
        {
            Row[i][MAP[i][j]] = true;
            Col[j][MAP[i][j]] = true;
            Square[(i / 3) * 3 + (j / 3)][MAP[i][j]] = true;
        }
    }
}

   이런식으로 !

3) 이제 밑그림은 다 그렸다. 본격적으로 백트래킹으로 들어갈 숫자들을 파악해보자.

   전체적인 구현 방법은 이렇다. 재귀호출을 통해서 구현을 할 건데, 9x9 총 81개의 칸에 대해서 재귀를 호출할 것이다.

   물론, 이미 0이 아닌 숫자들에 대해서는 아무것도 하지 않고 재귀호출만 해주면 된다.

   만약 0인 자리에 대해서라면, 1~9의 모든 숫자들을 반복문을 통해서 확인해 볼 것이다.

   여기서 확인해야할 것은

   1. 지금 넣고자 하는 가로줄에 해당 숫자가 없는지?

   2. 지금 넣고자 하는 세로줄에 해당 숫자가 없는지?

   3. 지금 넣고자 하는 사각형에 해당 숫자가 없는지?

   이 3개에 대해서만 확인을 해주면 된다. 물론, 우리는 이 과정을 위해서, 각 가로줄과 세로줄, 사각형에 있는 숫자들을

   true로 표시해두었다. 즉, 현재 넣고자 하는 위치의 가로줄,세로줄,사각형의 해당 값이 false라면 넣어볼 수 있는 것이다.

   만약, 넣을 수 있다면, 그 값을 넣고, 가로,세로,사각형에 그 숫자가 들어왔음을 표시를 해놔야 한다.

   하지만, 그 들어왔다고 그 결과값을 끝까지 들고가서는 안된다. 왜냐하면, 그 숫자가 아닐수도 있기 때문이다.

   해당 가로줄,세로줄,사각형에 그 숫자가 없다고 그 숫자를 답으로 단정지어 버리면 안된다는 것이다.

   그 숫자로 인해서 다른 칸이 성립이 안될 수도 있는 것이고, 또 다른 정답이 있을 수도 있기 때문이다.

   즉, 다시 해당값이 들어왔다는 표시를 해제해주는 작업도 필요한 것이다.

if (MAP[x][y] == 0)
{
    for (int i = 1; i <= 9; i++)
    {
        if (Row[x][i] == false && Col[y][i] == false && Square[(x / 3) * 3 + (y / 3)][i] == false)
        {
            Row[x][i] = true;
            Col[y][i] = true;
            Square[(x / 3) * 3 + (y / 3)][i] = true;
            MAP[x][y] = i;
            DFS(Cnt + 1);
            MAP[x][y] = 0;
            Row[x][i] = false;
            Col[y][i] = false;
            Square[(x / 3) * 3 + (y / 3)][i] = false;
        }
    }
}
else DFS(Cnt + 1);
 
 

    또한, 본인의 소스코드를 참고해보면 DFS() 함수의 매개변수는 int형 변수 하나이다.

    즉 DFS(0) ~ DFS(81)까지 재귀 호출을 하게 되는데, 이 때 x좌표 y좌표는

    매개변수값 / 3 = x좌표 , 매개변수값 % 3 = y좌표가 된다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 9
using namespace std;
 
int MAP[MAX][MAX];
bool Row[MAX][MAX];
bool Col[MAX][MAX];
bool Square[MAX][MAX];
 
void Input()
{
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] != 0)
            {
                Row[i][MAP[i][j]] = true;
                Col[j][MAP[i][j]] = true;
                Square[(i / 3) * 3 + (j / 3)][MAP[i][j]] = true;
            }
        }
    }
}
 
void Print()
{
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            cout << MAP[i][j] << " ";
        }
        cout << endl;
    }
}
 
void DFS(int Cnt)
{
    int x = Cnt / MAX;    // x 좌표
    int y = Cnt % MAX;    // y 좌표
    
    if (Cnt == 81)
    {
        Print();
        exit(0);
    }
 
    if (MAP[x][y] == 0)
    {
        for (int i = 1; i <= 9; i++)
        {
            if (Row[x][i] == false && Col[y][i] == false && Square[(x / 3) * 3 + (y / 3)][i] == false)
            {
                Row[x][i] = true;
                Col[y][i] = true;
                Square[(x / 3) * 3 + (y / 3)][i] = true;
                MAP[x][y] = i;
                DFS(Cnt + 1);
                MAP[x][y] = 0;
                Row[x][i] = false;
                Col[y][i] = false;
                Square[(x / 3) * 3 + (y / 3)][i] = false;
            }
        }
    }
    else DFS(Cnt + 1);
}
 
void Solution()
{
    DFS(0);
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}