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

https://programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환 | 프로그래머스

bfs최소 거리이긴 한데 그래프를 만드는과정이 좀 참신했다.!

 

#include <string>
#include <vector>
#include <queue>
#include <iostream>
 
using namespace std;
 
bool One_dis(string a,string b){
    int cnt=0;
    for(int i=0;i<a.size();i++){
        if(a[i]!=b[i]) cnt++;
    }
    if(cnt==1) return true;
    else return false;
}
 
int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    bool flag = false;
    for(int i=0;i<words.size();i++){
        if(words[i]==target){
            flag=true;
        }
    }
    if(!flag) return 0;
    
    vector<vector<int>> map(words.size()+1,vector<int>(words.size()+1));
    for(int i=1;i<words.size()+1;i++){
        if(One_dis(begin,words[i-1])) map[0][i]=1,map[i][0]=1;
    }
    for(int i=0;i<words.size();i++){
        for(int j=i;j<words.size();j++){
            if(i==j) continue;
            if(One_dis(words[i],words[j])) map[i+1][j+1]=1,map[j+1][i+1]=1;
        }
    } //그래프 만들기!!!
    int isV[52];
    for(int i=0;i<words.size()+1;i++) isV[i]=-1;
    queue<int> q;
    q.push(0);
    isV[0]=0;
    
    while(!q.empty()){
        int v=q.front();q.pop();
        for(int i=1;i<words.size()+1;i++){
            if(isV[i]==-1 && map[v][i]==1){
                isV[i] = isV[v]+1;
                q.push(i);
                if(words[i-1]==target) return isV[i];
            }
        }
    }
    
    return answer;
}