[BOJ/백준][Gold5] 2666 : 벽장문의 이동 (C++)

 

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

2666번: 벽장문의 이동

 

 

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

[풀이]
N제한이 20이므로 재귀를 이용한 브루트포스로 해결이 가능하다.

sol(n,cnt) 는 n번째 벽장을 사용할 차례일 때, 현재까지 cnt번 움직인 상태이다.

a[20] 배열에는 현재 열려있는 벽장은 1, 닫혀있는 벽장은 0으로 상태가 저장되어있다.
seq[i]는 i번째로 움직일 벽장의 번호이다.
sol(n,cnt)에서

a[seq[n]]이 1이라면 이미 열려있으므로 cnt 증가 없이 sol(n+1,cnt)으로 넘어가면 되고,

아니라면 벽장을 좌측 또는 우측으로 밀어야 하므로 열려있는 벽장의 인덱스를 idx에 저장한 뒤
우측 : sol(n+1,idx-cur+cnt)
좌측 : sol(n+1,cur-idx+cnt)

위와 같이 재귀함수를 진행해 나가면 답을 찾을 수 있다.

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N,M,a[20],seq[20],ans=9e8;
void sol(int n,int cnt){
    if(n==M){
        ans=min(ans,cnt);
        return;
    }
    int cur = seq[n];
    if(a[cur]){
        sol(n+1,cnt);
    }else{  
        int idx=-1;
        for(int i=cur;i<N;i++){
            if(a[i]){
                idx=i;
                break;
            }
        }
        if(idx!=-1){
            a[cur]=1;
            a[idx]=0;
            sol(n+1,idx-cur+cnt);
            a[cur]=0;
            a[idx]=1;
        }
        idx=-1;

        for(int i=cur;i>=0;i--){
            if(a[i]){
                idx=i;
                break;
            }
        }     
        if(idx!=-1){
            a[cur]=1;
            a[idx]=0;
            sol(n+1,cur-idx+cnt);
            a[cur]=0;
            a[idx]=1;
        }
    }
}
int main(){
    int t1,t2;
    scanf("%d%d%d%d",&N,&t1,&t2,&M);
    a[t1-1]=a[t2-1]=1;
    for(int i=0;i<M;i++){
        int v;
        scanf("%d",&v);
        seq[i]=v-1;
    }
    sol(0,0);
    printf("%d",ans);
}

 

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