BOJ 1035

25 Mar 2020 • ProblemSolving

조각 움직이기

문제출처

문제 해석

  • 최대 5개의 조각이 있는 5x5크기의 보드가 있을 때, 모든 조각이 연결되기위해 최소로 이동해야하는 수를 구하는 문제입니다.
  • 각 조각은 상하좌우로 이동할 수 있습니다.

설계(X)

  • 범위가 적어서 완전탐색으로 구현이 가능해 보였습니다.O((5x5)^5)
  • 그럼에도 불구하고 어떤식으로 구현을 해야할 지 감이 잡히지 않았습니다.
  • 해당 블로그에서 아이디어를 얻는데 도움을 받았습니다.
  • 모든 조각의 위치를 저장해 놓고, 조각들이 놓여져있는 모든 상태를 조사하게 됩니다.
  • 조각을 놓으면서, 해당 조각이 이동하는데 드는 거리는 Hamming distance로 구하게 됩니다.
  • 조각들을 모두 놓았을 때, dfs를 이용하여 모두 하나로 연결이 되어있는지 체크합니다.
  • 위의 방법만으로도 구현이 충분히 가능합니다만, 최적화를 위해서 재귀를 돌때 dist가 ans값보다 크면 볼 것도 없으므로 return도록 구현합니다.

구현(X)

코드
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

typedef pair<int,int> P;
#define MAXN 5
#define INF 987654321

P coord[MAXN];
char map[MAXN][MAXN];
bool visited[MAXN][MAXN];
int idx;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int ans = INF;
bool flag;
int cnt;
int calc_dist(int x1, int y1, int x2, int y2){
    return abs(x1-x2)+abs(y1-y2);
}
void dfs(int x, int y){
    if (flag) return;
    if (cnt >= idx){
        flag = true;
        return;
    }
    for (int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || ny < 0|| nx>=MAXN || ny>=MAXN) continue;
        if (map[nx][ny]=='*'&&!visited[nx][ny]){
            visited[nx][ny] = true;
            cnt++;
            dfs(nx,ny);
        }
    }
}
void go(int cur, int dist){
    if (!ans || dist > ans) return;
    if (cur == idx){
        cnt = 0;
        flag = false;
        memset(visited,false,sizeof(visited));
        for (int i = 0;i<MAXN*MAXN; i++){
            if (map[i/MAXN][i%MAXN]=='*') {
                visited[i/MAXN][i%MAXN] = true;
                cnt++;
                dfs(i/MAXN,i%MAXN);
                break;
            }
        }
        if (flag){
            if (ans> dist) {
                ans = dist;
            }
        }
        return;
    }
    for (int i= 0; i< MAXN; i++){
        for (int j =0;j<MAXN; j++){
            if (map[i][j] =='.'){
                map[i][j] = '*';
                go(cur+1,dist+calc_dist(coord[cur].first,coord[cur].second,i,j));
                map[i][j] = '.';
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    for (int i =0 ;i<MAXN; i++){
        cin >> map[i];
        for (int j =0;j<MAXN; j++){
            if (map[i][j] =='*'){
                map[i][j] = '.';
                coord[idx++] = {i,j};
            }
        }
    }
    go(0,0);
    cout << ans <<"\n";
    return 0;
}
디버깅
제출결과
  • 24ms

마무리

  • 완전탐색문제였습니다. 발상을 약간 전환시켜야 했던 문제였던 것 같습니다.
 BOJ

Related Posts