Minimum Genetic Mutation

몸도 풀겸 좀 가볍게 문제를 풀어봤다. 이 문제는 예전에 hit hot dot cog 이런식으로 단어 찾기 문제랑 그냥 똑같은 문제다. 단어를 하나씩만 바꿀 수 있다고 할때 bank안에 있는 단어로 변환 후에 BFS 탐색으로 endgGene 까지 도달하면은 쉽게 찾을 수 있는 문제다. 역시 BFS를 할때는 struct를 사용하면서 검색해주는게 제일 좋은거같다.

요즘 많이 회사 일이 바빴지만 이제부터라도 조금씩 문제 풀면서 성장하고 싶다.

class Solution {
    struct Items{
        string gene; 
        int dist; 
    };
    
public:
    bool check(string&a , string& b){
        int cnt = 0; 
        for(int i = 0; i < b.length(); i++){
            if(a[i] != b[i]) ++cnt; 
            if(cnt > 1) return false; 
        }
        return true; 
    }
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        if(startGene == endGene) return 0; 
        map<string,int> hashMap; 
        queue<Items> q; 
        q.push({startGene,0}); 
        
        while(!q.empty()){
            int size = q.size(); 
            for(int i = 0; i < size; i++){
                Items first = q.front();
                q.pop(); 
                string gene = first.gene; 
                int dist = first.dist; 
                
                if(gene == endGene) return dist; 
                
                for(string& s : bank){
                    if(!hashMap.count(s) && check(gene,s)){
                        q.push({s,dist+1}); 
                        hashMap[s]++; 
                    }
                }
            }
        }
        return -1; 
    }
};