BOJ 9207번: 페그 솔리테어

문제

문제 바로가기> BOJ 9207번: 페그 솔리테어

9207번: 페그 솔리테어

 

풀이

문제가 잘 이해되지 않았다,, 푸는 것보다 이해하는 데 오래 걸렸다 ,,

테스트 케이스 1번에 대해 다음과 같이 핀이 3번 이동하는 것이다!!

###...###
..oo.....
.....oo..
.........
###...###

###...###
....o....
....o....
.........
###...###

###...###
....o....
.........
.........
###...###

 

#include<iostream>
#define R 5
#define C 9
using namespace std;

int pinCnt, minPin;

char map[R][C];
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

void init(){
    pinCnt = 0;
    minPin = R*C;
}

void input(){
    for (int i = 0; i < R; i++){
        for (int j = 0; j < C; j++){
            cin >> map[i][j];
            if(map[i][j] == 'o') pinCnt++;
        }
    }
}

void backtracking(int pin){
    
    minPin = min(pin, minPin); // ans update

    for (int r = 0; r < R; r++){
        for (int c = 0; c < C; c++){
            if(map[r][c]!='o') continue;
            for (int d = 0; d < 4; d++){
                int nr = r + dr[d];
                int nc = c + dc[d];
                if(nr<0 || nr>=R || nc<0 || nc>=C || map[nr][nc]!='o') continue;

                int nnr = r + dr[d] * 2;
                int nnc = c + dc[d] * 2;
                if(nnr<0 || nnr>=R || nnc<0 || nnc>=C || map[nnr][nnc]!='.') continue;
                map[nnr][nnc] = 'o';
                map[r][c] = map[nr][nc] = '.';
                backtracking(pin - 1);
                map[nnr][nnc] = '.';
                map[r][c] = map[nr][nc] = 'o';
            }
        }
    }
}

int main(){
    freopen("../input.txt", "r", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    int N; cin >> N;
    while (N--){
        init();
        input();
        backtracking(pinCnt);
        cout << minPin << " " << pinCnt-minPin << "\n";
    }
}