[ BOJ 백준 1035번 - 조각 움직이기 ] 해설 및 코드

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

목적

5x5 크기의 보드에서 최대 5개의 조각을 움직여 서로 인접하도록 만드는 최소 이동 횟수를 구한다.

 

접근법

1. 다음과 같은 순으로 조각들의 가능한 모든 위치를 검사한다.

조각이 4개인 경우 탐색 순서

2. 위와 같이 배치한 조각들이 서로 인접해 있는지 검사한다.

(좌측 최상단에 있는 조각을 기준으로 dfs 방식으로 인접한 조각의 개수를 구하고 전체 조각의 개수와 비교)

3. 모든 조각이 서로 인접해있다면 조각 별 이동거리를 합하여 최소 이동거리를 갱신한다.

 

#include<iostream>
#include<vector>
#include<cstring>
#define f(a,b) for(int a=0;a<b;++a)
 
using namespace std;
 
struct pos{int i,j;};
vector<pos> v;
int minDist, d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
bool used[5][5], visited[5][5];
 
int count(pos p){
    int i=p.i,j=p.j;
    visited[i][j]=true;
    int cnt=1;
    f(k,4){
        int ni=i+d[k][0],nj=j+d[k][1];
        if(ni==-1||nj==-1||ni==5||nj==5||!used[ni][nj]||visited[ni][nj])continue;
        cnt+=count({ni,nj});
    }
    return cnt;
}
 
pos findFirstPos(){
    f(i,5)f(j,5)if(used[i][j])return {i,j};
    return {-1,-1};
}
 
bool possible(){
    memset(visited,false,sizeof(visited));
    return count(findFirstPos())==v.size();
}
 
void bruteForce(int n,int dist){
    if(dist>=minDist)return;
    
    if(n==v.size()){
        if(possible())if(minDist>dist)minDist=dist;
        return;
    }
    
    f(i,5)f(j,5){
        if(used[i][j])continue;
        
        used[i][j]=true;
        bruteForce(n+1,dist+abs(i-v[n].i)+abs(j-v[n].j));
        used[i][j]=false;
    }
}
 
void init(){
    string s[5];
    f(i,5)cin>>s[i];
    f(i,5)f(j,5)if(s[i][j]=='*')v.push_back({i,j});
    minDist=50;
    memset(used,false,sizeof(used));
}
 
int main(){
    init();
    bruteForce(0,0);
    cout<<minDist<<endl;
    
    return 0;
}