uva 10150번 Doublets

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() 을 통해 정확한 단어를 삽입했다

 

#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();
        visit.insert(str);
        if (visit_size == visit.size()) continue;
 
        for (int i = 0; i < dict.size(); i++) {
            if (check(str, dict[i])) {
                visit_size = visit.size();
                visit.insert(dict[i]);
                if (visit_size != visit.size()) {
                    visit.erase(dict[i]);
                    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;
}