[BOJ]9207_페그 솔리테어

문제를 이해하는데 조금 어려웠습니다.

 

게임판에 핀이 나란히 있고 다음칸이 비어있다면 두 핀은 모두 사라지고 다음칸에 핀이 생깁니다.

첫번째 TC : 

###...###
..oo.....
.....oo..
.........
###...###
moveCnt 0 , pinCnt 4
=>

###...###
....o....
.....oo..
.........
###...###
moveCnt 1 , pinCnt 3
=>

###...###
....o....
....o....
.........
###...###
moveCnt 2 , pinCnt 2
=>

###...###
.........
....o....
.........
###...###
moveCnt 3 , pinCnt 1

게임의 규칙과 위의 TC에서 알 수 있듯이 한번 이동할때 마다 pin은 하나씩 사라집니다.

 

 

최소움직임의 경우를 구하는 문제인 만큼 BFS를 떠올렸고 게임의 전체 정보를 저장할 info 구조체를 만들었습니다.

typedef vector<vector<char>> vvc;

typedef struct _info{
    vvc board;			
    int pinCnt;
    int moveCnt;
}info;

게임의 정보를 저장할때 핀의 위치정보만 비트마스킹과 같은 방식을 통해 저장하는 방식을 고민해 보았지만 잘 떠오르지 않았습니다.

 

다른 분들의 풀이를 보고 다시 생각해보니 이 문제는 핀의 최소 개수와 그 개수를 만들기 위해 필요한 최소 이동 횟수를 구하는 문제이므로 사실상 가능한 움직임 중 최대 이동 횟수를 구하는 문제입니다.  

 

따라서 BFS와 DFS (백트래킹) 모두 시간 복잡도 측면에서는 동일하지만 queue를 활용하는 BFS가 공간적으로 더 좋지 않습니다. 하지만 visited를 저장하여 중복되는 가지를 자르는 아이디어는 BFS,DFS모두 동일하게 적용이 가능합니다.

#include <iostream>
#include <queue>
#include <vector>
#include <set>

#define ROW 5
#define COL 9

using namespace std;

typedef vector<vector<char>> vvc;
vvc board;
set<vvc> visited;

int TC;
int pinCnt;

void input(){
    for(int r= 0 ; r < ROW ; r++){
        for(int c= 0 ;  c<COL ;c++){
            cin>>board[r][c];
            if(board[r][c]=='o') pinCnt++;
        }
    }
}

typedef struct _info{
    vvc board;
    int pinCnt;
    int moveCnt;
}info;

//D,U,R,L
int dy[4] = {1,-1,0,0};
int dx[4] = {0,0,1,-1};

bool isValid(int r, int c){
    return r>=0 && r<ROW && c>=0 && c<COL;
}

vvc moveBoard(vvc board, int r, int c, int d){
    int tr1 = r+dy[d];
    int tc1 = c+dx[d];
    int tr2 = r+2*dy[d];
    int tc2 = c+2*dx[d];

    board[r][c] = '.';
    board[tr1][tc1] = '.';
    board[tr2][tc2] = 'o';

    return board;
}

void solve(){
    info init;
    visited.insert(board);

    init.board = board;
    init.pinCnt = pinCnt;
    init.moveCnt = 0;

    queue<info> q;
    q.push(init);

    int minPinCnt;
    int minMoveCnt;

    while(!q.empty()){
        info pos = q.front();
        q.pop();
        vvc cur = pos.board;
        minPinCnt = pos.pinCnt;
        minMoveCnt = pos.moveCnt;

        for(int r= 0 ;r < ROW; r++){
            for(int c= 0 ;c < COL ; c++){
                if(cur[r][c]=='o'){
                    for(int d= 0; d< 4 ;d ++){
                        int tr1 = r+dy[d];
                        int tc1 = c+dx[d];
                        int tr2 = r+2*dy[d];
                        int tc2 = c+2*dx[d];

                        if(isValid(tr2,tc2)  && cur[tr2][tc2]=='.'&& cur[tr1][tc1] =='o'){
                            vvc moved = moveBoard(cur,r,c,d);
                            if(visited.find(moved)==visited.end()){
                                visited.insert(moved);
                                q.push({moved,pos.pinCnt-1,pos.moveCnt+1});
                            }
                        }
                    }
                }
            }
        }
    }

    printf("%d %d\n", minPinCnt, minMoveCnt);
}

void clear(){
    visited.clear();
    pinCnt = 0;
}

int main(){
    cin>>TC;
    board = vector<vector<char>>(ROW, vector<char>(COL,'.'));

    for(int i = 0 ; i < TC ; i++){
        input();
        solve();
        clear();
    }
}