백준 9207번 - 페그 솔리테어

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

게임판과 핀이 주어졌을 때, 핀을 이동시켜서 핀의 개수를 최소로 해야 하는 문제이다.

처음 문제를 봤을 때, 이해를 하는데 오래 걸렸는데 포인트를 파악하고 해결할 수 있었다.

먼저 두핀이 연속으로 있으면서 다음 방향에는 빈칸이어야 하는 것이다.

다음으로 맵은 변하지 않기 때문에 크기 제한이 적어서 DFS를 통해 문제를 해결해도 시간초과가 나지 않는 것이다.

문제의 분류는 백트래킹으로 되어 있는데, 나는 문제를 풀 때 방향설정을 한 뒤에

pin의 개수와 이동회수만 업데이트 해주는 식으로 해서 특별히 백트래킹 처리를 해주지는 않았다.

#include <iostream>
#include <math.h>
using namespace std;
 
const int len_y=5;
const int len_x=9;
 
char map[len_y][len_x]={0};
int ans_pin=0; //최소 핀의 개수
int ans_move=0; //최소 이동 회수
 
int dy[4]={1,-1,0,0};
int dx[4]={0,0,1,-1};
 
void dfs(int y,int x,int pin,int move){
    
    if(pin<=ans_pin){
        
        //다른 경로로 이동해서 이전 pin개수와 같을 때
        if(pin==ans_pin){
            if(ans_move!=0) //처음 이동한게 아닐 때
                ans_move=min(ans_move,move);
        }
        else{
            ans_pin=pin;
            ans_move=move;
        }
    }
    
    for(int dir=0;dir<4;dir++){
                
        int ny=y+dy[dir];
        int nx=x+dx[dir];
        
        if(ny<0 || ny>=len_y || nx<0 || nx>=len_x)
            continue;
        
        if(map[ny][nx]!='o')
            continue;
        
        int ny2=ny+dy[dir];
        int nx2=nx+dx[dir];
        
        if(ny2<0 || ny2>=len_y || nx2<0 || nx2>=len_x)
            continue;
        
        if(map[ny2][nx2]!='.')
            continue;
        
        
        map[y][x]='.';
        map[ny][nx]='.';
        map[ny2][nx2]='o';
        
        for(int i=0;i<len_y;i++)
            for(int j=0;j<len_x;j++)
                //ny2,nx2에서 'o'로 업데이트 해줘서 다음번에서 ans_pin과 ans_move 무조건 업데이트 된다.
                if(map[i][j]=='o')
                    dfs(i,j,pin-1,move+1);
        
        //복구
        map[y][x]='o';
        map[ny][nx]='o';
        map[ny2][nx2]='.';
            
    }
    
}
 
int main(){
    
    std::ios_base::sync_with_stdio(false);
    
    int N=0;
    cin>>N;
    
    for(int testCase=0;testCase<N;testCase++){
        
        ans_pin=0;
        ans_move=0;
        
        int pin=0;
        for(int i=0;i<len_y;i++)
            for(int j=0;j<len_x;j++){
                cin>>map[i][j];
                if(map[i][j]=='o')
                    pin++;
            }
        
        ans_pin=pin;
        for(int i=0;i<len_y;i++){
            for(int j=0;j<len_x;j++){
                if(map[i][j]=='o'){
                    dfs(i,j,pin,0);
                }
            }
        }
        printf("%d %d\n",ans_pin,ans_move);
    }
    
    return 0;
}