알고리즘
평범하게 BFS하면 되는데, 방문 표시를 어떻게 하느냐가 이번 문제의 관건이다.
난 각 기둥의 문자열 사이에 “/” 라는 문자를 추가하여 상태를 구분짓고, 이것을 set에 저장하였다.
이렇게 상태를 구분지어본 것은 처음이라, 코드를 짜면서도 계속 내 코드를 의심했다
코드
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
93
94
95
96
#include <iostream>
#include <queue>
#include <set>
using namespace std;
struct node {
string str[3];
int cnt;
};
int num[3];
queue<node> q;
set<string> s;
string sumNode(node n) {
return n.str[0] + "/" + n.str[1] + "/" + n.str[2];
}
bool check(node n) {
char c[3] = { 'A', 'B', 'C' };
for (int i = 0; i < 3; i++) {
for (int j = 0; j < n.str[i].size(); j++)
if (n.str[i][j] != c[i])
return false;
}
return true;
}
int main() {
int a;
node temp;
for (int i = 0; i < 3; i++) {
cin >> a;
if (a != 0)
cin >> temp.str[i];
else
temp.str[i] = "";
}
temp.cnt = 0;
for (int i = 0; i < 3; i++) {
for(int j =0; j< temp.str[i].size(); j++)
switch (temp.str[i][j]) {
case 'A':
num[0]++;
break;
case 'B':
num[1]++;
break;
default:
num[2]++;
break;
}
}
q.push(temp);
s.insert(sumNode(temp));
while (!q.empty()) {
node t = q.front();
q.pop();
int sizes[3] = { t.str[0].size(), t.str[1].size() , t.str[2].size() };
if (sizes[0] == num[0] && sizes[1] == num[1] && sizes[2] == num[2]) {
if (check(t)) {
cout << t.cnt;
return 0;
}
}
for (int i = 0; i < 3; i++) {
int size = sizes[i];
if (size != 0) {
char last = t.str[i][size - 1];
t.str[i].pop_back();
for (int j = 0; j < 3; j++) {
if (i != j) {
t.str[j] += last;
string sum = sumNode(t);
auto iter = s.find(sum);
if (iter == s.end()) {
s.insert(sum);
q.push({ {t.str[0], t.str[1], t.str[2]}, t.cnt + 1 });
}
t.str[j].pop_back();
}
}
t.str[i] += last;
}
}
}
}