[boj : 9207] 페그 솔리테어

[문제] : https://www.acmicpc.net/problem/9207

9207번: 페그 솔리테어

 

[분류]:백트래킹,브루트 포스

 

조건 :

수평,수직 방향으로 인접한 핀이 존재해야 하며,인접한 핀의 다음 칸은 비어 있어야 해당 핀이 인접한 핀을 넘어 이동이 허용이 된다.

 

과정 :

1)핀이 존재 한다면 인접한 핀이 있는지 검사(범위 체크)

2)인접한 핀의 다음 칸이 비어있는 지 검사 (범위 체크)

3)해당 조건이 전부 충족이 되었으면 핀을 이동 후 재귀 실행 (판을 갱신)

4)검사가 한번 다 끝나면 값들을 갱신해 준 후 돌아와서 판을 전 상태로 돌려 놓고 다시 위의 과정을 반복

 

구현 방법:

다른 백트래킹 문제와 큰 차이점은 없어 보입니다.

핀이 이동한 총 회수는 삭제한 핀의 개수와 일치하니 각 테스트마다 시작할때 핀의 개수를 먼저 구해준 후(ans) 탐색이 끝나면 이동한 횟수를 빼주면 남아있는 핀의 개수가 됩니다.(ans-ans2)

 

소스:

#include<bits/stdc++.h>
 
using namespace std;
 
int ans, ans2;
char Map[101][101];
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
 
void dfs(int x);
void Count();
 
int main()
{
    int n;
    cin >> n;
 
    while (n--)
    {
        ans2 = 0;
        for (int i = 0; i < 5; i++)
            scanf("%s", Map[i]);
        Count();
        dfs(0);
        cout << ans-ans2 << " " << ans2 << "\n";
    }
    return 0;
}
void Count()
{
    ans = 0;
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 9; j++)
            if (Map[i][j] == 'o')
                ans++;
}
 
void dfs(int x)
{
    for (int k = 0; k < 5; k++)
    {
        for (int i = 0; i < 9; i++)
        {
            if (Map[k][i] == 'o')
            {
                for (int j = 0; j < 4; j++)
                {
                    int tdx = k + dx[j];
                    int tdy = i + dy[j];
 
                    if (tdx < 0 || tdx >= 5 || tdy < 0 || tdy >= 9)continue;
 
                    if (Map[tdx][tdy] == 'o')
                    {
                        int ttdx = tdx + dx[j];
                        int ttdy = tdy + dy[j];
 
                        if (ttdx < 0 || ttdx >= 5 || ttdy < 0 || ttdy >= 9)continue;
 
                        if (Map[ttdx][ttdy] == '.')
                        {
                            Map[k][i] = Map[tdx][tdy] = '.';
                            Map[ttdx][ttdy] = 'o';
                            dfs(x + 1);
                            Map[k][i] = Map[tdx][tdy] = 'o';
                            Map[ttdx][ttdy] = '.';
                        }
                    }
                }
            }
        }
    }
    ans2 = max(ans2, x);
 
    return;
}

 

#어색한 표현이나 설명이 틀린부분 그리고 필요 없는 코드가 존재한다면 언제라도 태클 걸어주시면 감사하겠습니다