백준 1035번 - 조각 움직이기

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

1035번: 조각 움직이기

# Approach)

전형적인 완전탐색 문제이다.

1) 보드의 처음 별모양의 위치를 벡터에 넣는다.

2) 그 순서대로 각 별모양이 어디로 이동할지 정하고 다음 별모양이 선택하도록 DFS탐색을 진행해준다.

 

# Time Complexity)

시간복잡도는 $_{25}\mathrm{P}_{5}$ $ = 5!{25 \choose 5} $ $= 6,375,600 < 10^9 $ 으로 2초안에 충분히 탐색이 가능하다.

 

일반적으로 보드의 크기가 $n^2$, 조각이 $m$개라고 하면 $_{n^2}\mathrm{P}_{m} $으로 매우 빠르게 증가할 것이다.

따라서 숫자가 작을땐 완전탐색 문제를 의심해보면 좋다. 

 

#Code(c++)

#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <stack>
#include <cmath>
#include <tuple>
#include <climits>
#include <fstream>
#include <sstream>
// #include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define command_param int argc, char *argv[]
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i < n; i++)
#define FOR(i, s, e) for(int i = s; i < e; i++)
#define pf first
#define ps second
#define pii pair<int,int> 
#define ll long long
#define lll __int128
#define endl "\n"
#define nulls '\0'
#define dkdk " "
const int INF = 987654321;
const ll INFLL = 1e13;
const int mod = (int)1e9+7;
const int N = 802;
const int st = 50;
// const int N = 1000000;
int n, m, t, k, cnt, ans = INF;
bool mm[5][5];
bool dmm[5][5];
bool visit[5][5];
int di[] = { -1, 0, 1, 0 };
int dj[] = { 0, 1, 0, -1 };
vector<pii> pv;

bool rck(int ci, int cj) { return ci >= 0 && cj >= 0 && ci < 5 && cj < 5; }

bool is_linked() {
  memset(visit, 0, sizeof(visit));
  int fnct = 0, ci, cj;
  for0(i, 5) for0(j, 5) if(dmm[i][j]) { ci = i; cj = j; break; }
  queue<pii> q; q.push({ ci, cj });
  while(!q.empty()) {
    auto p = q.front(); q.pop();
    if(visit[p.pf][p.ps]) continue;
    visit[p.pf][p.ps] = true;
    fnct++;
    for0(k, 4) {
      int ai = p.pf + di[k], aj = p.ps + dj[k];
      if(!rck(ai, aj) || !dmm[ai][aj]) continue;
      q.push({ai, aj});
    }
  }
  return fnct == cnt;
}

void dfs(int i, int move) {
  if(ans <= move) return;
  if(i == cnt) {
    if(is_linked()) ans = min(ans, move);
    return;
  }
  for0(ci, 5) {
    for0(cj, 5) {
      if(dmm[ci][cj]) continue;
      dmm[ci][cj] = 1;
      dfs(i+1, move + abs(pv[i].pf - ci)+abs(pv[i].ps-cj));
      dmm[ci][cj] = 0;
    }
  }
}

int main() {
  FASTIO; 
  for0(i, 5) {
    string s; cin >> s;
    for0(j, 5) if(s[j] == '*') {
      mm[i][j] = 1;
      cnt++;
      pv.push_back({ i, j });
    }
  }
  dfs(0, 0);
  cout << ans;
}