[백준] 페그 솔리테어

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

9207번: 페그 솔리테어

우선 문제부터 간단하게 요약하면, 

 

게임을 하게 되는데, 핀은 최대 8개까지 있고, 핀은 이웃한 핀을 건너뛸수 있고, 이렇게 건너 뛴 경우 뛰임 당한 핀은 사라집니다. 이런 문제에서 이야기한 게임을 진행한 후, 남은 핀의 갯수와 최소 이동횟수를 출력해야 합니다.

 

<Solution>

핀의 위치를 기록해두고, dfs를 이용하여 문제를 해결할 수 있습니다.

 

핀이 건너뛸 수 있는 경우를 생각해보면, 매 핀은 상하좌우 4방향을 탐색합니다. 만약 이웃한 곳에 핀이 있다면, 그 다음 공간도 살펴보고, 그 다음 공간이 빈 공간이라면 점프가 가능합니다. 

 

이 로직을 구현하면 됩니다. 하지만 핀의 위치를 기록해두게 되면, 건너뛰는 경우, 건너뛰는 핀과, 건너뛰임 당하는 핀이 모두 변화가 생깁니다. 그래서 저같은 경우, 핀이 최대 8개라고 하였기 때문에 for loop를 순회하여 핀을 찾는 형태로 구현하였습니다.

 

하지만 이 부분을 조금 더 개선하자면, 핀 뿐만 아니라 map(게임판) 도 확인하여, 만약 핀이 있고 '.' ( 빈공간 ) 으로 마킹된 경우 이 경우를 진행하지 않는 형태로 구현하여도 됩니다.

 

실제 구현은 아래와 같습니다.

#include <iostream>
using namespace std;
#define MAXH (5)
#define MAXW (9)
char map[MAXH+2][MAXW+2];
int solremain, solmove;

int pins[8][2]; // pin 1번의 r,c -> pin[0][0] pin[0][1]
int num_pins;

int d_row[] = {1, -1, 0, 0};
int d_col[] = {0, 0, 1, -1};

void InputData(){
    for (int h=1; h<=MAXH; h++){
        cin >> &map[h][1];
    }
}

void dfs(int mvcnt){

    // // for debug
    // cout << "@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@" << endl;
    // for(int r = 1; r<=MAXH; r++){
    //     for(int c = 1; c<=MAXW; c++){
    //         cout << map[r][c];
    //     }
    //     cout << endl;
    // }
    // // for debug
    // for(int i = 0; i<8; i++){
    //     cout << "pos pins" << endl;
    //     cout << pins[i][0] << ' ' << pins[i][1] << endl;
    // }

    // 아무것도 못움직이는 경우 return해줘야함
    // find which pins can move
    int move_flag = 0;
    for(int i = 0; i<8; i++){
        // 움직일수 있는지 check
        int r = pins[i][0];
        int c = pins[i][1];
        if(r == -1) continue;

        for(int j = 0 ; j< 4; j++){
            if(map[r+d_row[j]][c+d_col[j]] == 'o'){

                // 다음 블록이 외부 아니여야함 + 빈공간이여야함
                if((1<=r+2*d_row[j] && r+2*d_row[j] <= 5 && 
                    1<= c+2*d_col[j] && c+2*d_col[j] <= 9) &&
                    map[r+2*d_row[j]][c+2*d_col[j]] == '.'){
                    
                    move_flag = 1;
                    num_pins-=1;
                    // array에서 핀 찾아서 제거
                    int k;
                    int a, b;
                    for(k = 0; k<8; k++){
                        if(pins[k][0] == r+d_row[j] && pins[k][1] == c+d_col[j]){
                            a = pins[k][0];
                            b = pins[k][1];
                            
                            pins[k][0] = -1;
                            pins[k][1] = -1;
                            break;
                        }
                    }

                    // 이동한 핀 
                    int a_,b_;
                    a_ = pins[i][0];
                    b_ = pins[i][1];
                    pins[i][0] = r+2*d_row[j];
                    pins[i][1] = c+2*d_col[j];

                    // map 수정
                    map[r][c] = '.';
                    map[r+d_row[j]][c+d_col[j]] = '.';
                    map[r+2*d_row[j]][c+2*d_col[j]] = 'o';

                    dfs(mvcnt+1);
                    // 원상복구
                    num_pins+=1;
                    pins[k][0] = a;
                    pins[k][1] = b;

                    pins[i][0] = a_;
                    pins[i][1] = b_;

                    map[r][c] = 'o';
                    map[r+d_row[j]][c+d_col[j]] = 'o';
                    map[r+2*d_row[j]][c+2*d_col[j]] = '.';

                }


            }

        }

    }
    if(move_flag == 0) {
        int cnt_pins = 0;
        for(int i = 0; i<8; i++){
            if(!(pins[i][0] == -1)) cnt_pins++;
        }
        if(solremain > cnt_pins){
            solremain = cnt_pins;
            solmove = mvcnt;
        }
        else if(solremain == cnt_pins){
            solmove = min(solmove, mvcnt);
        }
        return;
    }

}

void solution(){
    solremain = 987654321;
    solmove = 0;
    // initialize
    for(int i =0; i<8; i++){
        for(int j = 0; j<2; j++){
            pins[i][j] = -1; // -1이면 핀없는것임
        }
    }
    num_pins = 0;

    // memorize pins
    for(int r = 1; r<=MAXH; r++){
        for(int c = 1; c<=MAXW; c++){
            if(map[r][c] == 'o'){
                pins[num_pins][0] = r;
                pins[num_pins][1] = c;

                num_pins++;
            }
        }
    }

    dfs(0);

}

int main(){
    int T;
    cin >> T;
    for (int t=1; t<=T; t++){
        InputData();

        solution();
        cout << solremain << " " << solmove << endl;
    }
    return 0;
}