[Algorithm]Baekjoon 9207번 :: 페그 솔리테어

https://www.acmicpc.net/problem/9207

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
int t, n;
char arr[5][9];
int dirs[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
 
bool IsValid(int y, int x)
{
    if (y < 0 || y == 5) return false;
    if (x < 0 || x == 9) return false;
 
    return true;
}
 
int curPinCount = 0;
int answerPinCount = 0;
int curMoveCount = 0;
int answerMoveCount = 0;
 
void DFS()
{
    bool check = false;
 
    for (int i = 0; i < 5; ++i)
    {
        for (int j = 0; j < 9; ++j)
        {
            if (arr[i][j] == 'o')
            {
                for (int d = 0; d < 4; ++d)
                {
                    int ny = i + dirs[d][0];
                    int nx = j + dirs[d][1];
                    int nny = i + dirs[d][0] * 2;
                    int nnx = j + dirs[d][1] * 2;
 
                    if (IsValid(ny, nx) && IsValid(nny, nnx))
                    {
                        if (arr[ny][nx] == 'o' && arr[nny][nnx] == '.')
                        {
                            check = true;
 
                            --curPinCount;
                            ++curMoveCount;
                            arr[i][j] = '.';
                            arr[ny][nx] = '.';
                            arr[nny][nnx] = 'o';
 
                            DFS();
                            
                            ++curPinCount;
                            --curMoveCount;
                            arr[i][j] = 'o';
                            arr[ny][nx] = 'o';
                            arr[nny][nnx] = '.';
                        }
                    }
                }
            }
        }
    }
 
    if (!check) // 더이상 옮길게 없었으면
    {
        if (curPinCount == answerPinCount)
        {
            answerMoveCount = min(answerMoveCount, curMoveCount);
        }
        else if (curPinCount < answerPinCount)
        {
            answerPinCount = curPinCount;
            answerMoveCount = curMoveCount;
        }
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> t;
 
    while (t--)
    {
        answerPinCount = 0;
        answerMoveCount = 0x3f3f3f3f;
 
        curPinCount = 0;
        curMoveCount = 0;
 
        for (int i = 0; i < 5; ++i)
        {
            for (int j = 0; j < 9; ++j)
            {
                cin >> arr[i][j];
                if (arr[i][j] == 'o') ++answerPinCount;
            }
        }
 
        curPinCount = answerPinCount;
 
        DFS();
 
        printf("%d %d\n", answerPinCount, answerMoveCount);
    }
}
 
 

 

 

페그솔리테어란 게임을 모티브로 한 문제이다.

최종적으로 핀들을 이리저리 옮겼을 때, 판에 남아있는 최소의 핀의개수와, 최소의 핀의개수일 때의 최소 이동횟수를 구하는 문제이다.

 

즉, 일단 최소핀의개수가 우선순위이고 그다음 최소이동횟수인 것이다.

 

그리고 일단 이전까지 풀었던 완전탐색유형같은 경우는 특정좌표에서 이리저리 체크한다음 다음좌표로 넘어가는 식인데, 이 문제같은 경우는 위로 핀을 옮길경우 해당 윗핀도 또 다시 탐색을 해야한다.

그렇기 때문에 매번 맵의 처음부터 끝까지 탐색하면서 찾아진 핀마다 계속 탐색을 수행하는것이다.

즉 매번 탐색에서의 좌표는 별 의미가 없다. 그래서 DFS함수에 매개변수가 아예 없다.

 

그리고 인접한 핀을 넘어갈 수 있다.. 라는것은 바로 옆에 딱 붙어있는 핀을 말한다.

난 혹시나해서 두칸,세칸떨어진 핀도 넘어갈 수 있는줄 알았는데 그런 문제는 아니였다.

좀 더 어렵게내면 그렇게 낼 수 있을지도? 물론 그러더라도 좀 더 귀찮아질뿐, 바로 이전에 풀었던 문제유형과 비슷해져서 크게 어려울 건 없다.