[ 백준 9207 ] 페그 솔리테어 (C++)

백준의 페그 솔리테어(9207) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 많이 어려웠던 문제이다. 이 문제를 해결하는 큰 틀과 그 이유 부터 정리해보고 구체적으로 알아보자.

   1. 핀을 한번 옮길 수 있을 때 마다 맵을 복사해주고(기존의 맵은 유지) 다음 핀을 옮기자.

   → 현재 옮길 수 있는 핀이 있다고 하더랃, 그 핀이 아닌 다른 핀을 움직이거나, 해당 핀을 다른 방향으로 움직일 경우

      움직이는 횟수가 달라질 수 있으므로 기존의 맵은 유지해줘야 한다.

   2. 1의 과정을 계속 반복하면서, 핀을 더이상 움직일 수 없을 때, 남아 있는 핀의 갯수와, 움직인 횟수를 비교해서 최소

     값을 찾아내자.

  

   본인은 움직이는 핀이 있을 때 마다, 맵을 복사해주고, 움직인 횟수를 Count해주기 위해서 함수에 매개변수 2개를 사용하였다.

   한 개는, 현재까지 움직인 횟수, 나머지 하나는 현재 맵 이 2개의 매개변수를 사용해주었다. (본문함수 : DFS)

   해당 함수 안에서는 Flag라는 핀을 더이상 움직일 수 있는지 없는지를 판단해주는 변수를 하나 사용해 주었고,

   더 이상 움직일 수 없는 경우에는, 기존의 핀의 갯수와 현재 핀의 갯수를 비교해주어서 더 작은 값으로 갱신해 주었고,

   움직인 횟수도 갱신해 주었다.

   즉, 기존의 핀의 갯수를 저장하는 변수(본문 : Hole_Num)이 하나 필요하고, 기존에 움직인 횟수를 저장하는 변수

   (본문 : Move_Cnt)가 필요하다.

   자세한 구현 내용은 소스코드를 참고하자.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
using namespace std;
 
char MAP[5][9];
 
int Hole_Num, Move_Cnt;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Initialize()
{
    Hole_Num = 987654321;
    Move_Cnt = 987654321;
}
 
void Input()
{
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void Copy_MAP(char A[][9], char B[][9])
{
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            A[i][j] = B[i][j];
        }
    }
}
 
void DFS(int M_Cnt, char Map[][9])
{
    bool Flag = false;
    char C_MAP[5][9];
 
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            if (Map[i][j] == 'o')
            {
                for (int k = 0; k < 4; k++)
                {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    int nnx = i + dx[k] + dx[k];
                    int nny = j + dy[k] + dy[k];
 
                    if (nnx >= 0 && nny >= 0 && nnx < 5 && nny < 9)
                    {
                        if (Map[nx][ny] == 'o' && Map[nnx][nny] == '.')
                        {
                            Flag = true;
                            Copy_MAP(C_MAP, Map);
                            C_MAP[i][j] = '.';
                            C_MAP[nx][ny] = '.';
                            C_MAP[nnx][nny] = 'o';
 
                            DFS(M_Cnt + 1, C_MAP);
                        }
                    }
                }
            }
        }
    }
 
    if (Flag == false)
    {
        int Cnt = 0;
 
        for (int i = 0; i < 5; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if (Map[i][j] == 'o') Cnt++;
            }
        }
 
        if (Cnt < Hole_Num)
        {
            Hole_Num = Cnt;
            Move_Cnt = M_Cnt;
        }
 
        else if (Cnt == Hole_Num && M_Cnt < Move_Cnt) Move_Cnt = M_Cnt;
    }
}
 
void Solution()
{
    DFS(0, MAP);
}
 
void Solve()
{
    int Tc;
    cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << Hole_Num << " " << Move_Cnt << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}