[백준] 백트래킹 - 9207. 페그 솔리테어

문제

페그 솔리테어는 구멍이 뚫려있는 이차원 게임판에서 하는 게임이다. 각 구멍에는 핀을 하나 꽂을 수 있다.

핀은 수평, 수직 방향으로 인접한 핀을 뛰어넘어서 그 핀의 다음 칸으로 이동하는 것만 허용된다. 인접한 핀의 다음 칸은 비어있어야 하고 그 인접한 핀은 제거된다.

현재 게임판에 꽂혀있는 핀의 상태가 주어진다. 이때, 핀을 적절히 움직여서 게임판에 남아있는 핀의 개수를 최소로 하려고 한다. 또, 그렇게 남기기 위해 필요한 최소 이동횟수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 1 ≤ N ≤ 100이 주어진다. 각 테스트 케이스는 게임판의 초기 상태이다.

게임판은 모두 같은 모양을 가진다. (예제 참고) '.'는 빈 칸, 'o'는 핀이 꽂혀있는 칸, '#'는 구멍이 없는 칸이다. 핀의 개수는 최대 8이며, 각 테스트 케이스는 빈 줄로 구분되어져 있다.

 

출력

각 테스트 케이스에 대해서, 핀을 움직여서 남길 수 있는 핀의 최소 개수와 그 개수를 만들기 위해 필요한 최소 이동 횟수를 출력한다.

 

예제 입력1

3
###...###
..oo.....
.....oo..
.........
###...###

###...###
..oo.o...
...o.oo..
...oo....
###...###

###o..###
.o.oo....
o.o......
.o.o.....
###...###

 

예제 출력1

1 3 

1 7 

1 7

 

생각

 

 

작성한 코드

#include <iostream>
 
using namespace std;
 
char map[6][10];
 
// 상, 하, 좌, 우
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
 
int p_num, m_num;
int num;
 
void dfs(int x, int y, int n){
    if(p_num == 0 || p_num > n){
        p_num = n;
        m_num = num - n;
    }
    
    for(int k=0; k<4; k++){
        // 다음 칸
        int nx = x+dx[k]; 
        int ny = y+dy[k];
        
        if(nx < 0 || ny < 0 || nx >= 5 || ny >=9 ) continue;
 
        // 다음 칸이 o이고  
        if(map[nx][ny] == 'o'){
            // 다음다음칸
            int nnx = nx + dx[k];
            int nny = ny + dy[k];
            if(nnx < 0 || nny < 0 || nnx >= 5 || nny >=9 ) continue;
 
            // 다음 다음 칸이 비어있으면
            if(map[nnx][nny] == '.'){
                map[x][y] = map[nx][ny] = '.';
                map[nnx][nny] = 'o';
 
                for(int i=0; i<5; i++){
                    for(int j=0; j<9; j++){
                        if(map[i][j] == 'o'){
                            dfs(i, j, n-1);
                        }
                    }
                }
                map[x][y] = map[nx][ny] = 'o';
                map[nnx][nny] = '.';
            }
        }
    }    
    return;
}
 
int main(int argc, const char * argv[]) {
    // insert code here...
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
 
    while(n--){
        p_num = m_num = 0;
        int cnt = 0; // 핀 개수 체크
        for(int i=0; i<5; i++){
            for(int j=0; j<9; j++){
                cin >> map[i][j];
                if(map[i][j]=='o') cnt ++;
            }
        }
        num = cnt;
        for(int i=0; i<5; i++){
            for(int j=0; j<9; j++){
                if(map[i][j] == 'o'){
                    dfs(i, j, cnt);
                }
            }
        }
 
        cout << p_num << " " << m_num << "\n";
    }
   
    return 0;
}