[C++/프로그래머스] 단어 변환

✅ LV. 3
🔖 BFS

✏️ 솔루션

1. words 에서 현재 단어와 한 문자 차이 나는 단어 찾기
   ➡️ bool check 함수: 현재 단어와 비교 단어가 한 문자 차이나면 true
2. 현재 단계와 탐색해 찾은 단어의 visit 비교해서 현재 단계가 더 낮을 떄만 큐(비교 단어 후보) 에 비교 단어push
3. visit 에 거리 기록 ➡️ words 의 단어를 모두 unodered_map 에 저장하고 visit 값은 0으로 초기화
   ➡️ unordered_map<string,int> visit: string 에 단어, int 에 visit 값 등록
   ❗️ words 의 단어들이 중복되지 않기 때문에 map 으로 구현 가능!
4. 현재 단어가 begin 이 아닐 때만 현재 단계를 현재 단어의 visit 값으로 등록
   ➡️ int v 함수: 단어가 저장되어 있는 visit 값을 조회를 빈번하게 하기 때문에 visit 값 조회하는 함수를 따로 구현
5. 현재 문자와 비교 문자가 한 글자 차이 날 경우
   1) 큐에 비교 문자 push
   2) 비교 문자의 visit 값을 step(현재 단계)+1 로 변경
   ❗️ 비교 단어의 visit 값이 0이 아니면서 현재 단계보다 작거나 같을 경우, 이미 최단거리 방법을 찾은 것이기 때문에 그 루트로 탐색하지 않기 위해 continue
6. 마지막에 target 의 visit 값을 answer 로 지정. target 이 words 에 없을 경우 0

📌 self feedback

• 반복적인 코드는 함수로 따로 빼줬는데 효율적인지는 잘 모르겠다.
• map 의 key 에 대한 값을 조회할 때 코드

auto it = map.find(key);
if(it!=map.end()) cout << it->first << it->second;

• 반드시 find 결과가 존재하는지 확인해야 함
• it->first: key 값
• it->second: value 값

✏️ 최종 code

#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <iostream>

using namespace std;

queue<string> q;
unordered_map<string,int> visit;

bool check(string begin, string str) {
    int cnt=0;
    for(int i=0;i<begin.size();i++) {
        if(begin[i]!=str[i]) cnt++;
    }
    if(cnt==1) return true;
    return false;
}

int v(string str) {
    auto it= visit.find(str);
        
    if(it!=visit.end()) return it->second;
    else return -1;
}

int bfs(string begin,int step,vector<string> words,string target) {
    q.push(begin);

    int k;
    while(!q.empty()) {
        begin=q.front();
        q.pop();

        if(v(begin)!=-1) step=v(begin);

        for(int i=0;i<words.size();i++) {
            string str=words[i];

            k=v(str);
            
            if(k!=0 && k<=step) continue;
            
            //한 글자 차이 날 경우
            if(check(begin,str)) {
                q.push(str);
                visit[str]=step+1;
            }   

        }
    }

    int res=v(target);
    if(res==-1) return 0;
    else return res;
    
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    
    for(int i=0;i<words.size();i++) {
        visit.insert({words[i],0});
    }
    
    answer=bfs(begin,0,words,target);
       
    return answer;
}