programmers 단어 변환

programmers : https://programmers.co.kr/learn/courses/30/parts/12421

 

깊이/너비우선탐색 level3 단어변환 문제입니다.

 

이 문제는 BFS를 이용해서 쉽게 해결할 수 있습니다.

풀이는 주석을 보시면 됩니다.

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
 
int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    int len = words.size();
    int wordlen = words[0].size();
 
    // bfs를 위한 queue 선언 ( 확인할 string, 횟수 )
    queue<pair<string, int> > q;
    // 해당 string을 사용했는지 안했는지 빠르게 알기위한 set visit
    set<string> visit;
 
    q.push({ begin, 0 });
 
    while (!q.empty()) {
        string str = q.front().first;
        int cnt = q.front().second;
        q.pop();
 
        // string compare => 0 일때 두 스트링은 같음
        // 같다는 의미는 가장 빠른 계산으로 찾아진 것이니 결국 답이됨
        if (str.compare(target) == 0) {
            answer = cnt;
            break;
        }
 
        for (int i = 0; i < len; i++) {
            int check = 0;
            // 두 단어간의 철자 차이를 계산
            for (int k = 0; k < wordlen; k++) {
                if (str[k] != words[i][k]) check++;
                if (check > 1) break;
            }
 
            // 철자가 1개만 틀리다면 이동가능
            // 이 때 이 단어를 방문했는지 안했는지 확인해줄 필요가 있다.
            // set을 사용해서 insert 후에 size를 비교하면 방문한 스트링인지 아닌지 쉽게 알 수 있다
            if (check == 1) {
                int pre = visit.size();
                visit.insert(words[i]);
                if (pre != visit.size()) q.push({ words[i], cnt + 1 });
            }
        }
 
    }
 
    return answer;
}