[ 백준 4574 ] 스도미노쿠 (C++)

백준 스도미노쿠(4574) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 스도쿠와 비슷한 문제지만, 한층 더 나아가서 스도쿠처럼 숫자 하나하나를 붙여넣는 게임이 아닌, 2개의 쌍으로 이루어진

   타일로 스도쿠를 채워야 하는 문제이다.

   먼저 본인은 이 문제를 백트래킹으로 구현했다. 사용한 변수부터 어떤 용도로 사용했는지 ,어떻게 사용할건지에 대해서

   부터 알아보도록 하자.

   스도미노쿠는 스도쿠와 게임방식은 똑같다. 각 열에 1 ~9 까지의 숫자가 하나씩, 각 행에 1 ~ 9 까지의 숫자가 하나씩,

   9 x 9 짜리 맵을 3 x 3 짜리 9개로 나누었을 때, 각각의 3 x 3 짜리 사각형에도 1 ~ 9 까지의 숫자가 하나씩 들어가도록

   만들어 주면 된다. 더 나아가서 스도미노쿠에서는 주어진 타일의 갯수도 관리해줄 필요가 있다.

   따라서 이 놈들을 관리하기 위해서 다음과 같은 변수들을 선언해 주었다.  

int MAP[MAX][MAX];                 // 숫자를 채워갈 스도쿠 맵.
bool Row[MAX][MAX + 1];            // 행에 들어가는 숫자를 관리.
bool Col[MAX][MAX + 1];            // 열에 들어가는 숫자를 관리.
bool Square[3][3][MAX + 1];        // 3x3 짜리 사각형에 들어가는 숫자를 관리.
bool Tile[MAX + 1][MAX + 1];       // 타일을 사용했는지를 관리.

   ( MAX = 9 입니다 ! )

   1. MAP은 말 그대로 맵이다. 스도쿠를 채워넣어야 할 2차원 배열이다.

   2. Row[][] 배열은 행에 들어가는 숫자를 관리하기 위한 배열이다.

     Row[a][b] = true 의 의미는 "현재, a행에 'b'라는 숫자는 이미 존재합니다." 이다.

   3. Col[][] 배열은 열에 들어가는 숫자를 관리하기 위한 배열이다.

     Col[a][b] = true 의 의미는 "현재, a열에 'b'라는 숫자는 이미 존재합니다." 이다.

   4. Square[][] 배열은 9 x 9 짜리 맵을 3 x 3 짜리 사각형 9개로 나누었을 때, 그 9개의 사각형을 좌표처럼 생각해서

     만들어 주었다.

    

     위의 그림과 같이 9개의 사각형을 저렇게 좌표로 표현해 본 것이다.

     따라서 배열의 크기를 Square[3][3][10] 으로 만들어 주었고, Square[a][b][c] = true의 의미는

     "현재 (a, b) 사각형에는 'c'라는 숫자는 이미 존재합니다" 를 의미한다.

     여기서 (a, b)는 9 x 9 짜리 맵에서의 좌표 (a, b)가 아닌 위의 그림과 같이 3x3짜리 9개의 사각형의 좌표를

     의미한다.

   5. 마지막으로 Tile 배열이다. 주어진 타일을 이용해서 스도미노쿠를 채워가야 하기 때문에, 어떤 타일을 썼는지

      안썼는지 또한 체크해주어야 한다.

      Tile[a][b] = true의 의미는 "{ a , b } 로 이루어진 타일을 이미 사용했습니다" 를 의미한다.

   위와 같은 변수들을 이용해서 문제를 풀어나갈 것이다.

  

2) 문제 풀이에 들어가기 전에 이번 풀이에서 내내 사용될 공식을 하나 알고가자 !

   ( 본인 코드 및 설명 기준으로는 가로를 y , 세로를 x로 둡니다 !

    (0 , 0 )에서 동쪽으로 움직이면 (0, 1) 이고 (0, 0)에서 남쪽으로 움직이면 (1, 0)으로 계산했습니다 ! )

   지금부터 저 9 x 9 짜리 맵을 좌표가 아닌 하나의 번호로 좌표에 접근할 것이다.

   예를 들어서 이런식이다. (0 , 0) = 0, (0 , 1) = 1 .... (8 , 8) = 81 이런식이다.

   그럼 현재 번호가 0일 때, 이 0이 (0 , 0 )이라는 것을 어떻게 알아낼 수 있을까 ??

   또한, 우리는 3x3짜리 사각형에서도 어느 사각형에 존재하는지 어떻게 알아낼 수 있을지에 대해서 먼저 알아보자.

   현재 번호가 0이다. 즉, 좌표로는 (0 , 0)에 들어가는 숫자를 정하려고 하는 상황이다.

   0 을 9로 나눈 값이 x좌표가 되고, 0을 9로 나눈 나머지 값이 y좌표가 된다.

   0을 9로 나눈 값은 = 0 , 0 을 9로 나눈 나머지 = 0 이므로 번호가 0일 때 이 0의 좌표는 (0 , 0) 이라는 것이다.

   현재 번호가 5일 때 해보자. 5 / 9 = 0 , 5 % 9 = 5. 즉 5는 (0 , 5)에 위치하는 좌표이다.

   즉, 우리는 현재 가진 숫자 만으로도 몇 행에, 몇 열에 존재하는지 알 수 있다.

   그럼 이제 어느 3x3 사각형에 있는지도 확인해보자.

   이 경우에는 지금까지 위한 좌표 값(x, y)를 둘다 3으로 나누어 주면 된다.

   번호가 0일 경우에는 (0, 0)에 존재하고, 3x3짜리 사각형 기준으로도 (0, 0) 3x3사각형에 들어가는 좌표이다.

   그럼 3으로 나눠보면 둘다 x, y 둘다 0이 나오게 되고 따라서 이는 3 x 3 사각형 중에서도 ( 0, 0) 에 해당하는 사각형에

   들어가는 좌표라는 것을 알 수 있다.

   번호가 5일 경우에는 (0, 5)에 존재하고, 3 x 3 짜리 사각형을 알기 위해서 둘다 3으로 나눠주면

   0 / 3 = 0 , 5 / 3 = 1 즉, (0 , 1) 3x3사각형에 존재하는 좌표라는 것을 알 수 있다.

   [ 번호로 전체 좌표 알아내기 ] : (x , y) = (번호 / 9 , 번호 % 9)

   [ 번호로 어느 3x3사각형에 위치하는지 알아내기 ] : 전체 좌표를 알아낸 후, (해당좌표 x / 3, 해당좌표 y / 3)

  

3) 이제 본격적으로 풀이에 들어가보자. 본인은 깊이우선탐색을 기반으로 한 백트래킹으로 접근을 했다.

   DFS함수를 호출할 때의 매개변수는 int Idx 라는 1개의 매개변수만 들고 관리를 해 주었다.

   이 Idx가 위에서 계속 말했던 "번호"이다. 즉, 처음에 0으로 호출되어서, 이 값이 81이 될 때까지, 즉 81번까지 간다면,

   다시말해서 81칸을 모두 채웠다면 출력시키고 종료하는 식으로 구현을 했다.

   전체적인 DFS 함수 내에서 진행되는 과정을 말하자면 다음과 같다.

   1. 번호를 통해서 어느 좌표값을 의미하는지 파악하기. ( 2)번에서 말한 공식 )

   2. 해당 좌표가 0이 아니라면, 즉 이미 숫자가 채워진 칸이라면 그 다음 칸으로 DFS 호출.

   3. 해당 좌표가 0이라면, 즉 아직 숫자가 채워지지 않았다면 가능한 타일을 찾아서 선택해준 후, 그 다음 칸으로 DFS 호출.

   4. 위의 과정 백트래킹.

   이렇게 표현할 수 있는데, 3번 과정을 구체적으로 알아보자.

   우리는 이제 타일에 대해서 생각을 좀 해봐야 한다. 타일은 회전이 가능하기 때문에, { 1 , 2 } 로 이루어진 타일이나

   { 2 , 1 } 로 이루어진 타일은 같은 타일이다.

   그럼 우린 하나의 타일로 4가지를 표현할 수 있다. (a, b)로 이루어진 타일이 있다고 생각해보면 다음과 같은

   4가지 경우가 존재하게 된다.

  

    이렇게 가로 2가지, 세로 2가지 경우가 존재한다.

    그래서 이 4가지 경우에 대해서 모두 백트래킹을 진행해 주었다.

    타일을 사용하게 되면 2칸을 한번에 차지하게 된다.

    가로로 놓을 경우, (x , y)에 하나의 타일을 놓는다고 가정하면, 결국 (x, y)와 (x, y + 1)을 채우게 된다.

    따라서, 이 좌표들에 따른, 행과 열, 그리고 3x3짜리 사각형에 해당 숫자가 있는지 모두 체크해 주어야 한다.

    세로로 놓을 경우, (x, y)에 하나의 타일을 놓는다고 가정하면, 결국 (x, y)와 (x + 1, y)를 채우게 된다.

    따라서, 이 좌표들 또한 위에서 말한 모든 경우를 체크해 주어야 한다.

    물론, "아직 사용하지 않은 타일이고, 타일을 사용할 수 있는 경우" 에 위의 조건들을 체크해줘야 한다.

    현재 좌표가 (0. 8)인데 가로로 타일을 놓는 것은 불가능하다. 즉, 이런경우를 모두 배제시켜 주어야 한다.

 

    코드가 생각보다 조금 길다. 따라서 복잡해보일 수 있지만 구현해야 할 내용이 많다기 보다는, 체크해줘야 할 것들이

    많아서 모두 하나하나 체크해 주다보니 길어졌다...

[ 소스코드 ]

#include<iostream>
#include<string>
#include<cstring>
 
#define endl "\n"
#define MAX 9
using namespace std;
 
int N, Tc;
int MAP[MAX][MAX];
bool Row[MAX][MAX + 1];    // 행
bool Col[MAX][MAX + 1];    // 열
bool Square[3][3][MAX + 1];
bool Tile[MAX + 1][MAX + 1];
bool Flag, Inp_Flag;
 
void Initialize()
{
    Flag = false;
    memset(MAP, 0, sizeof(MAP));
    memset(Row, false, sizeof(Row));
    memset(Col, false, sizeof(Col));
    memset(Square, false, sizeof(Square));
    memset(Tile, false, sizeof(Tile));
}
 
void Input()
{
    cin >> N;
    if (N == 0)
    {
        Inp_Flag = true;
        return;
    }
    
    for (int i = 0; i < N; i++)
    {
        int Num1, Num2;
        string Pos1, Pos2;
        cin >> Num1 >> Pos1 >> Num2 >> Pos2;
 
        int x = Pos1[0] - 'A';
        int y = Pos1[1] - '0' - 1;
        int xx = Pos2[0] - 'A';
        int yy = Pos2[1] - '0' - 1;
 
        Tile[Num1][Num2] = true;
        Tile[Num2][Num1] = true;
        
        MAP[x][y] = Num1;
        MAP[xx][yy] = Num2;
 
        Row[x][Num1] = true;
        Row[xx][Num2] = true;
 
        Col[y][Num1] = true;
        Col[yy][Num2] = true;
 
        Square[x / 3][y / 3][Num1] = true;
        Square[xx / 3][yy / 3][Num2] = true;
    }
 
    for (int i = 1; i <= 9; i++)
    {
        string Pos; cin >> Pos;
        int x = Pos[0] - 'A';
        int y = Pos[1] - '0' - 1;
 
        Row[x][i] = true;
        Col[y][i] = true;
        Square[(x / 3)][(y / 3)][i] = true;
        MAP[x][y] = i;
    }
}
 
bool Check(int x, int y, int N1, int N2, char C)
{    
    if (C == 'G')    
    {
        /* C = 'G' 일 경우 가로로 놓는 경우 Check. */
        /* (x, y)에 N1과 N2가 붙어있는 타일을 가로로 놓는다. */
        /* = (x, y)에 N1을 (x, y + 1)에 N2를 놓는다. */
 
        if (Row[x][N1] == true || Row[x][N2] == true) return false;
        if (Col[y][N1] == true || Col[y + 1][N2] == true) return false;
        if (Square[x / 3][y / 3][N1] == true || Square[x / 3][(y + 1) / 3][N2] == true) return false;
        return true;
    }
    else
    {
        /* C = 'S'일 경우 세로로 타일을 놓는 경우 Check.
         * (x, y)에 N1과 N2가 붙어있는 타일을 세로로 놓는다.
         * = (x , y)에 N1을, (x + 1, y)에 N2를 놓는다.
         */
        if (Row[x][N1] == true || Row[x + 1][N2] == true) return false;
        if (Col[y][N1] == true || Col[y][N2] == true) return false;
        if (Square[x / 3][y / 3][N1] == true || Square[(x + 1) / 3][y / 3][N2] == true) return false;
        return true;
    }
}
 
void MakeVisit(int x, int y, int N1, int N2, char C, bool T)
{
    Tile[N1][N2] = T;
    Tile[N2][N1] = T;
 
    if (C == 'G')
    {
        Row[x][N1] = Row[x][N2] = T;
        Col[y][N1] = Col[y + 1][N2] = T;
        Square[x / 3][y / 3][N1] = Square[x / 3][(y + 1) / 3][N2] = T;
 
        if (T == true)
        {
            MAP[x][y] = N1;
            MAP[x][y + 1] = N2;
        }
        else MAP[x][y] = MAP[x][y + 1] = 0;
    }
    else
    {
        Row[x][N1] = Row[x + 1][N2] = T;
        Col[y][N1] = Col[y][N2] = T;
        Square[x / 3][y / 3][N1] = Square[(x + 1) / 3][y / 3][N2] = T;
 
        if (T == true)
        {
            MAP[x][y] = N1;
            MAP[x + 1][y] = N2;
        }
        else MAP[x][y] = MAP[x + 1][y] = 0;
    }
}
 
void Print()
{
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            cout << MAP[i][j];
        }
        cout << endl;
    }
}
 
void DFS(int Idx)
{
    if (Flag == true) return;
    if (Idx == 81)
    {
        Flag = true;
        cout << "Puzzle " << Tc << endl;
        Print();
        return;
    }
 
    int x = Idx / MAX;
    int y = Idx % MAX;
 
    if (MAP[x][y] != 0) DFS(Idx + 1);
    else
    {
        if (y <= 7 && MAP[x][y + 1] == 0)
        {
            for (int i = 1; i <= 9; i++)
            {
                for (int j = i + 1; j <= 9; j++)
                {
                    if (Tile[i][j] == false)
                    {
                        if (Check(x, y, i, j, 'G') == true)
                        {
                            MakeVisit(x, y, i, j, 'G', true);
                            DFS(Idx + 2);
                            MakeVisit(x, y, i, j, 'G', false);
                        }
 
                        if (Check(x, y, j, i, 'G') == true)
                        {
                            MakeVisit(x, y, j, i, 'G', true);
                            DFS(Idx + 2);
                            MakeVisit(x, y, j, i, 'G', false);
                        }
                    }
                }
            }
        }
 
        if (x <= 7 && MAP[x + 1][y] == 0)
        {
            for (int i = 1; i <= 9; i++)
            {
                for (int j = i + 1; j <= 9; j++)
                {
                    if (Tile[i][j] == false)
                    {
                        if (Check(x, y, i, j, 'S') == true)
                        {
                            MakeVisit(x, y, i, j, 'S', true);
                            DFS(Idx + 1);
                            MakeVisit(x, y, i, j, 'S', false);
                        }
 
                        if (Check(x, y, j, i, 'S') == true)
                        {
                            MakeVisit(x, y, j, i, 'S', true);
                            DFS(Idx + 1);
                            MakeVisit(x, y, j, i, 'S', false);
                        }
                    }
                }
            }
        }
    }
}
 
void Solution()
{
    DFS(0);
}
 
void Solve()
{
    Tc = 1;
    while (1)
    {
        Initialize();
        Input();
        if (Inp_Flag == true) break;
        Solution();
        Tc++;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}