[BOJ/백준][Gold5] 9207 : 페그 솔리테어 (C++)

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

9207번: 페그 솔리테어

 

 

[난이도] Gold5
[유형] 브루트포스

[풀이]
핀의 개수가 최대 8개밖에 되지 않기 때문에 핀의 위치를 저장한 set, 보드의 상태를 저장한 vector를
파라미터로 하는 백트래킹 함수를 짜주면 완전탐색으로 답을 구할 수 있습니다.

 

 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
int tc,dy[4]={-1,1,0,0},dx[4]={0,0,1,-1},ans,ansc;
void sol(vector<string> b,set<pair<int,int>> p,int cnt){
    if(ans>p.size()){
        ans=p.size();
        ansc=cnt;
    }else if(ans==p.size() && ansc>cnt) ansc=cnt;
    for(auto [y,x] : p){
        for(int i=0;i<4;i++){
            int ny=y+dy[i],nx=x+dx[i];
            if(ny<0||nx<0||ny>=5||nx>=9||b[ny][nx]!='o') continue;
            int nny=ny+dy[i],nnx=nx+dx[i];
            if(nny<0||nnx<0||nny>=5||nnx>=9||b[nny][nnx]!='.') continue;
            auto tb=b;
            auto tp=p; 
            tb[y][x]='.';
            tb[ny][nx]='.';
            tb[nny][nnx]='o';
            tp.insert({nny,nnx});
            tp.erase({ny,nx});
            tp.erase({y,x});
            sol(tb,tp,cnt+1);
        }
    }
}
int main(){
    cin >> tc;
    while(tc--){
        ans=9e8,ansc=9e8;
        vector<string> board;
        set<pair<int,int>> p;
        for(int i=0;i<5;i++){
            string s;
            cin >> s;
            board.push_back(s);
            for(int j=0;j<s.size();j++){
                if(s[j]=='o') p.insert({i,j});
            }
        }
        sol(board,p,0);
        cout << ans << " " << ansc << "\n";
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/9207.cpp