[C언어] 9207. 페그 솔리테어

14620 꽃길이랑 정답률 비슷하길래 쉬운줄 알았는데 풀었더니...후...어렵다.

접근 법.

1. O로 표시되어 있는 곳들의 모든 움직임을 탐색한 후에, O가 최소가 될 때의 움직임 횟수를 구하면 된다.

그럼 어떻게 모든 움직임을 탐색할 수 있을까??

반복문으로 O가 있으면 그냥 백트랙킹으로 움직였다. 빽 했다를 반복하면 된다! 이렇게 모든 O에 대해 탐색해보면 정답이 나온다.

기존의 재귀와는 다르게 딱히 재귀의 종료 기준이라 해야되나, 갑자기 생각이 안 나는데. 조건에서 벗어나면 재귀 그만 들어가게 하는 그런 조건문이 없는 것 같다. 아마도.....

#include <stdio.h>
#include <string.h>
 
int dx[] = { 0,0,-1,1 }, dy[] = { -1,1,0,0 };
int MOVE_MIN, COUNT_MIN;
int Check(char arr[5][10])
{
    int count = 0;
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            if (arr[i][j] == 'o')
                count++;
        }
    }
    return count;
}
 
int DFS(char map[5][10], int n)
{
    char copy[5][10];
    int MIN;
 
    //printf("\n");
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            copy[i][j] = map[i][j];
            //printf("%c", copy[i][j]);
        }
        //printf("\n");
    }
 
    for (int a = 0; a < 5; a++)
    {
        for (int j = 0; j < 9; j++)
        {
            if (copy[a][j] == '.' || copy[a][j] == '#')
                continue;
 
            int y = a;
            int x = j;
            //printf("y : %d  x : %d \n", y, x);
            for (int i = 0; i < 4; i++)
            {
                int yy = y + dy[i];
                int xx = x + dx[i];
 
                if (yy > 5 || yy < 0 || xx > 9 || xx < 0)
                    continue;
 
                if (copy[yy][xx] == 'o')
                {
                    //printf("yy : %d  xx : %d \n", yy, xx);
                    switch (i)
                    {
                    case 0://상
                        if (yy - 1 >= 0 && copy[yy - 1][xx] == '.')
                        {
                            //printf("상\n");
                            copy[yy - 1][xx] = 'o';
                            copy[yy][xx] = copy[y][x] = '.';
                            DFS(copy, n + 1);
                            copy[yy - 1][xx] = '.';
                            copy[yy][xx] = copy[y][x] = 'o';
                        }
                        break;
                    case 1://하
                        if (yy + 1 < 5 && copy[yy + 1][xx] == '.')
                        {
                            //printf("하\n");
                            copy[yy + 1][xx] = 'o';
                            copy[yy][xx] = copy[y][x] = '.';
                            DFS(copy, n + 1);
                            copy[yy + 1][xx] = '.';
                            copy[yy][xx] = copy[y][x] = 'o';
                        }
                        break;
                    case 2://좌
                        if (xx - 1 >= 0 && copy[yy][xx - 1] == '.')
                        {
                            //printf("좌\n");
                            copy[yy][xx - 1] = 'o';
                            copy[yy][xx] = copy[y][x] = '.';
                            DFS(copy, n + 1);
                            copy[yy][xx - 1] = '.';
                            copy[yy][xx] = copy[y][x] = 'o';
                        }
                        break;
                    case 3://우
                        if (xx + 1 < 9 && copy[yy][xx + 1] == '.')
                        {
                            //printf("우\n");
                            copy[yy][xx + 1] = 'o';
                            copy[yy][xx] = copy[y][x] = '.';    
                            DFS(copy, n + 1);
                            copy[yy][xx + 1] = '.';
                            copy[yy][xx] = copy[y][x] = 'o';
                        }
                        break;
                    }
                }
            }
        }
    }
 
    MIN = Check(copy);
 
    if (MIN < COUNT_MIN)
    {
        COUNT_MIN = MIN;
        MOVE_MIN = n;
    }
 
 
    return;
}
 
int main()
{
    int Test_Case;
    scanf("%d", &Test_Case);
 
    for (int T = 1; T <= Test_Case; T++)
    {
        int count = 0;
        char arr[5][10] = { NULL };
        MOVE_MIN = COUNT_MIN = 987654321;
 
        for (int i = 0; i < 5; i++)
            scanf("%s", arr[i]);
 
        DFS(arr, 0);
 
        printf("%d %d\n", COUNT_MIN, MOVE_MIN);
    }
 
    return 0;
}