[ 백준 3967 ] 매직스타 (C++)

백준의 매직스타(3967) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 이 문제는, 별 모양의 12개의 칸에서, 빈칸에 알맞은 숫자를 넣어서 직선을 이루는 4개의 숫자를 합쳤을 때 26이 되도록

   구현하는, 백트래킹 문제이다.

   어떻게 문제를 해결했는지 순차적으로 알아보자. (절대 정답이 아닌, 주관적인 본인의 풀이 입니다)

   먼저, 12개의 칸에 들어가는 숫자가 모두 다르다. 따라서, 입력으로 주어지는 숫자는 건드리거나 또 선택하면 안된다.

   따라서, 본인은 12개의 숫자들이 선택되었는지 아닌지를 판단하기 위해서 Select[] 라는 bool형 배열을 하나 사용하였다.

   즉, 입력으로 주어지는 맵에서 'A' ~ 'L' 사이로 주어지는 값들은 입력과 동시에  Select[] = true 로 설정해주었다.   

   또한, 우리가 채워야 하는 칸의 갯수를 파악하기 위해서 'x'로 입력되는 칸의 갯수를 입력과 동시에 Count 해 주었다.

   그리고 'x'에는 우리가 알파벳을 채워 넣어야 하기 때문에, 맵에서 그 위치를 알아야 한다. 

   따라서, 본인은 입력을 받을 때, 그 위치를 Vector를 하나 생성해서 저장해 두었다.

   입력되는 맵이, 애초에 별 모양만 입력되는 것이 아닌, 사각형 모양으로 입력이 주어지기 때문에 위와 같이 위치를 저장해주는

   부분을 구현하였다.

  

   지금까지 우리가 초기에 설정해놓은 일과, 앞으로 해야할 일을 정리해보자.

   [ 우리가 지금까지 설정해놓은 일 ]

   1. 'A' ~ 'L' 사이로 입력되는 값들은 Select[] 배열을 통해서, 이미 선택된 값이므로 더 이상 선택하지 마라는 의미로

      표시를 해 두었다.

   2. 우리가 총 몇칸을 채워야 하는지를 알기 위해서 'x'의 갯수를 Count해 두었고, 'x'로 입력되는 부분의 좌표를 저장해 두었다.

   [ 우리가 앞으로 해야할 일 ]

   1. 순열을 구하는 방식을 통해서 'x'의 모든 칸을 채워줘야 한다.

   - 순열을 사용하는 이유는 순서에 영향을 미치기 때문이다. 예를 들어서 1,2,3,4,5 번 칸이 'x'인데, 1,2,3,4,5번 칸에

     1,2,3,4,5를 넣어줄 때의 결과와 5,4,3,2,1을 넣어줄 때의 결과는 다르기 때문에 순서에 영향을 미친다.

     따라서 순열을 구하는 방식을 통해서, 남은 숫자들을 순열로 구현해줘야 한다.

     순열을 구하는 방식을 잘 모른다면 아래의 링크를 타고 읽어보고 오자 !

     [ 순열 구현하기 자세히 알아보기(Click) ]

   

    2. 'x'의 갯수만큼 순열을 구현했다면, 직선을 이루는 4개의 숫자들의 합이 26을 이루는지 확인해줘야 한다.

    3. 정답의 조건을 만족한다면 프로그램 종료, 그게 아니라면 다른 순열을 찾아서 다시 확인해봐야 한다.

2) 순열을 구현하는 방법은 위의 링크를 통해서 충분히 알았을 것이라 생각한다. 그렇다면, 이 문제에서는 순열을 어떻게 적용시키

   는지 알아보자.

   우리는 애초에 'x'가 있는 좌표를 Vector에 저장해 두었다고 했다. 즉, MAP에 있는 'x'를 특정 값으로 바꿔버리는 것이다.

   순열을 조합하는 방법을 그대로 사용하되, MAP에 있는 좌표를 바꾸는 방식으로 구현해야 한다는 의미이다.

  

    이런식으로 구현해줘야 한다.

    순열이 하나 만들어 졌다면, 이제 정답을 체크하기만 하면 된다. 정답을 체크하는 방법은 한 직선에 있는 4개의 변의 합이

    26이 되는지만 확인해 주면 된다. 이부분은 어렵지 않으니 소스코드를 참고하도록 하자.

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
using namespace std;
 
char MAP[5][9];
bool Select[13];
int X_cnt;
 
vector<pair<int, int>> V;
 
void Input()
{
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            cin >> MAP[i][j];
            if ('A' <= MAP[i][j] && MAP[i][j] <= 'L')
            {
                Select[MAP[i][j] - 'A'] = true;
            }
            else if (MAP[i][j] == 'x')
            {
                V.push_back(make_pair(i, j));
                X_cnt++;
            }
        }
    }
}
 
bool CheckMAP()
{
    if ((MAP[0][4] - 'A' + 1) + (MAP[1][3] - 'A' + 1) + (MAP[2][2] - 'A' + 1) + (MAP[3][1] - 'A' + 1) != 26) return false;
    if ((MAP[0][4] - 'A' + 1) + (MAP[1][5] - 'A' + 1) + (MAP[2][6] - 'A' + 1) + (MAP[3][7] - 'A' + 1) != 26) return false;
    if ((MAP[1][1] - 'A' + 1) + (MAP[1][3] - 'A' + 1) + (MAP[1][5] - 'A' + 1) + (MAP[1][7] - 'A' + 1) != 26) return false;
    if ((MAP[3][1] - 'A' + 1) + (MAP[3][3] - 'A' + 1) + (MAP[3][5] - 'A' + 1) + (MAP[3][7] - 'A' + 1) != 26) return false;
    if ((MAP[4][4] - 'A' + 1) + (MAP[3][3] - 'A' + 1) + (MAP[2][2] - 'A' + 1) + (MAP[1][1] - 'A' + 1) != 26) return false;
    if ((MAP[4][4] - 'A' + 1) + (MAP[3][5] - 'A' + 1) + (MAP[2][6] - 'A' + 1) + (MAP[1][7] - 'A' + 1) != 26) return false;
 
    return true;
}
 
void Print_MAP()
{
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            cout << MAP[i][j];
        }
        cout << endl;
    }
}
 
void DFS(int Idx, int Cnt)
{
    if (Cnt == X_cnt)
    {
        if (CheckMAP() == true)
        {
            Print_MAP();
            exit(0);
        }
        return;
    }
 
    for (int i = 0; i < 12; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        MAP[V[Idx].first][V[Idx].second] = i + 'A';
        DFS(Idx + 1, Cnt + 1);
        MAP[V[Idx].first][V[Idx].second] = 'x';
        Select[i] = false;
    }
}
 
void Solution()
{
    DFS(0, 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;
}