uva : https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1091
doublets 의 의미는 한 쌍의 단어를 비교했을 떄 알파벳이 1개만 다른 단어의 쌍을 말한다
[aaa, aab] 같은 경우가 됨
문제풀이는 다음과 같다
1. 단어의 사전이 개행이 나오기 전까지 주어진다
2. 단어의 한 쌍이 주어진다
3. 주어진 한 쌍 중에서 첫번째 단어에서 두번째 단어로 가는 가장 짧은 경로를 찾는다
4. EOF가 아니면 2번부터 다시 반복한다
일단 최단경로에 관한 문제이기 때문에 bfs로 접근했다
탐색과정은 다음과 같다
1. bfs탐색은 현재 단어를 기준으로 방문하지 않은 doublets string을 찾았다.
2. end string을 발견하면 bfs 종료 후 탐색해왔던 string을 찾는다.
아 참고로 문제 인풋이 좀 더러운 문제였다
사전이 주어질 때 단어 뒤에 ' ' 형태의 공백이 같이 딸려오는 인풋이 있어서 pop_back() 을 통해 정확한 단어를 삽입했다
|
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <string>
#include <cstring>
using namespace std;
struct pii {
string my_str;
int my_cnt;
int my_num;
};
vector<string> dict;
int arr[30000];
bool check(string a, string b) {
if (a.size() != b.size()) return false;
int cnt = 0;
for (int i = 0; i < a.size(); i++) {
if (a[i] != b[i]) cnt++;
if (cnt > 1) return false;
}
if (cnt == 1) return true;
return false;
}
vector<string> solve(string start, string end, int pin) {
set<string> visit;
queue<pii> q;
vector<pair<string,int> > btr;
vector<string> answer;
int last_pin;
bool sol = false;
q.push({ start,0,pin});
while (!q.empty()) {
string str = q.front().my_str;
int cnt = q.front().my_cnt;
int my_num = q.front().my_num;
q.pop();
if (str.compare(end) == 0) {
sol = true;
last_pin = my_num;
break;
}
int visit_size = visit.size();
if (visit_size == visit.size()) continue;
for (int i = 0; i < dict.size(); i++) {
if (check(str, dict[i])) {
visit_size = visit.size();
if (visit_size != visit.size()) {
q.push({ dict[i], cnt + 1, i});
if (arr[i] == -1) arr[i] = my_num;
}
}
}
}
if (!sol) return answer;
else {
answer.push_back(end);
while (1) {
string str = dict[arr[last_pin]];
answer.push_back(str);
if (str.compare(start) == 0) break;
last_pin = arr[last_pin];
}
return answer;
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
string str, start, end;
while (getline(cin, str), str != "") {
while (1) {
if (str[str.size() - 1] == ' ') str.pop_back();
else break;
}
dict.push_back(str);
}
while (cin >> start >> end) {
memset(arr, -1, sizeof(arr));
if (start.size() != end.size()) {
cout << "No solution.\n\n";
continue;
}
if (start.compare(end) == 0) {
cout << end << "\n" << end << "\n\n";
continue;
}
int pin;
for (int i = 0; i < dict.size(); i++) {
if (start.compare(dict[i]) == 0) {
pin = i;
break;
}
}
vector<string> answer = solve(start, end, pin);
if (answer.size() == 0) cout << "No solution.\n";
else for (int i = answer.size() - 1; i >= 0; i--) cout << answer[i] << "\n";
cout << "\n";
}
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
'algorithm > uva' 카테고리의 다른 글
| uva 11994번 Happy Painting! (0) | 2020.04.06 |
|---|---|
| uva 384번 Slurpys, BOJ 14906번 스러피 (0) | 2020.03.31 |
| uva 10469번 To Carry or not to Carry (0) | 2020.03.23 |
| uva 10010번 Where's Waldorf? (0) | 2020.03.23 |
| uva 679 - Dropping Balls (0) | 2020.03.19 |