https://www.acmicpc.net/problem/1035
# Approach)
전형적인 완전탐색 문제이다.
- 보드의 처음 별모양의 위치를 벡터에 넣는다.
- 그 순서대로 각 별모양이 어디로 이동할지 정하고 다음 별모양이 선택하도록 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++)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#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;
}