문제
동일한 길이의 두 문자열의 차이가 한 글자만 있는 경우 Doublet이라 한다.
단어사전에 해당하는 문자열이 한줄에 하나씩 나열되며, 두 문자열이 공백을 기준으로 나뉘어져 입력이 들어오게되면 출력을 해야함을 의미한다.
출력은 입력으로 들어온 두 문자열 중에서 앞의 것을 시작 단어, 뒤의 것을 끝 단어로 둔다.
시작단어부터 현재 단어와 Doublet관계에 있는 단어를 타고 다음 단어로 이동이 가능하다.
끝 단어에 도착하게 되면 지금껏 타고온 단어들을 순서대로 출력해야한다. (단, 제일 빠르게 끝 단어에 도착한 순서를 출력해야한다. )
문자열의 최대길이는 16이며, 입력되는 단어의 최대개수는 25143개 이다.
booster
rooster
boosted
roaster
coasted
roasted
coastal
postal
booster roasted예를 들어 위와 input이 들어오게되면 먼저 booster의 Doublet을 찾는다.
rooster
boosted찾아진 Doublet을 가지고 또 Doublet관계에 있는 단어를 찾는다.
rooster
=> roaster
boosted
=> 없음.
위의 과정을 반복하여 끝 단어인 roasted에 제일 빠르게 도착하는 경로의 순서를 출력해야한다.
booster -> rooster -> roaster -> roasted
만약 시작단어에서 끝단어로 가는 경우가 존재하지 않을 경우 No solution. 을 출력한다.
풀이.
먼저 No solution. 에 해당하는 경우를 생각해줬다.
- 시작단어와 끝 단어의 길이가 다른경우.
- 시작단어 또는 끝 단어가 단어사전에 없는 경우.
- Doublet을 통하여 끝 단어에 도달할 수 없는 경우.
위의 세 가지 경우를 No solution. 에 해당하는 경우로 뒀다.
이제 출력이 가능한 경우에 대하여 살펴보자!
- 먼저 단어사전의 각 단어들의 이전 문자열을 기록하는 배열을 만들었다.
- 시작단어( 끝 단어 )의 길이와 같은 문자열을 단어사전에서 찾아 새로운 큐 ( Sub_Dictionary ) 로 생성했다.
- 현재 다루는 단어와 Doublet관계에 놓인 문자열을 Sub_Dictionary에서 탐색한다.
- 탐색된 문자열을 Sub_Dictionary에서 제외하고, 이전 문자열로 현재 기준이 되는 문자열을 기록한다.
- 탐색된 문자열을 큐에 삽입해가면서 1~4의 과정을 반복하고, 그 사이에 만약 끝 단어와 Doublet 관계에 놓인 문자열을 발견하면 반복을 종료, 순서를 출력한다.
코드는 여기에..
더보기
#include<iostream>
#include<string>
#include<vector>
#include<queue>
using namespace std;
#pragma warning(disable:4996);
int Parent[25143];
string StartWord, EndWord;
string WordDictionary[25143];
vector<string> OUTPUT;
bool HasInclude(string now, int size) {
for (int i = 0; i < size;i++) {
if (now == WordDictionary[i]) return true;
}
return false;
}
int isDoublet(string Comparator, string Target) {
int counter = 0;
for (int i = 0; i < Comparator.size(); i++) {
if (Comparator[i] != Target[i]) counter++;
}
return counter;
}
void solve(int DictionarySize) {
if (StartWord.length() != EndWord.length()) return;
if (HasInclude(StartWord, DictionarySize) == false || HasInclude(EndWord, DictionarySize) == false) return;
queue<int>Sub_Dictionary;
int StartWordIdx;
// 길이가 동일한 단어 솎아내기
for (int i = 0; i < DictionarySize; i++) {
string item = WordDictionary[i];
if (item == StartWord) {
StartWordIdx = i;
}
if (item.length() == StartWord.length()) {
Sub_Dictionary.push(i);
}
}
Parent[StartWordIdx] = -1;
queue<int> words;
words.push(StartWordIdx);
while (!words.empty()) {
int now = words.front();
words.pop();
string value = WordDictionary[now];
if (isDoublet(value, EndWord) < 2) {
OUTPUT.push_back(EndWord);
while (Parent[now] != -1) {
string value = WordDictionary[now];
OUTPUT.push_back(value);
now = Parent[now];
}
OUTPUT.push_back(StartWord);
break;
}
int size = Sub_Dictionary.size();
for (int i = 0; i < size; i++) {
int nxt = Sub_Dictionary.front();
Sub_Dictionary.pop();
string nxt_value = WordDictionary[nxt];
if (value == nxt_value) continue;
if (isDoublet(value, nxt_value) < 2) {
Parent[nxt] = now;
words.push(nxt);
continue;
}
Sub_Dictionary.push(nxt);
}
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
string str;
int end = 0;
int count = 0;
while (getline(cin, str)) {
int space = str.find(" ");
if (space < str.length()) {
if (count > 0) {
cout << '\n';
}
EndWord = str.substr(space + 1, str.length());
StartWord = str.substr(0, space);
OUTPUT.clear();
solve(end);
if(OUTPUT.size() < 2){
cout << "No solution.\n";
}
else {
while (!OUTPUT.empty()) {
cout << OUTPUT.back() << '\n';
OUTPUT.pop_back();
}
}
count++;
}
else {
WordDictionary[end] = str;
end++;
}
}
return 0;
}