프로그래머스 단어 변환

다익스트라

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int MAX_NUM = 100000000;
vector<vector<int>> GraphEdges;

vector<int> Dijkstra(int start)
{
    vector<int> Dist;
    for(int i = 0 ; i < GraphEdges.size(); i++) Dist.push_back(MAX_NUM);
    Dist[start] = 0;
    queue<int> q;
    q.push(start);
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        for(int i = 0 ; i < GraphEdges[cur].size(); i++)
        {
            int originalDest = Dist[GraphEdges[cur][i]];
            // cout << originalDest << endl;
            if(Dist[cur] + 1 < originalDest)
            {
                // cout << cur << " " << GraphEdges[cur][i];
                Dist[GraphEdges[cur][i]] = Dist[cur] + 1;
                q.push(GraphEdges[cur][i]);
            }
        }
    }
    return Dist;
}

int solution(string begin, string target, vector<string> words) {
    // Make Edges
    words.push_back(begin);
    GraphEdges = vector<vector<int>>(words.size());
    
    for(int i = 0; i < words.size(); i++)
    {
        for(int j = 0; j < words.size(); j++)
        {
            if(i==j) continue;
            int diff = 0;
            for(int p = 0; p < words[i].size(); p++)
            {
                if(words[i][p] != words[j][p]) diff++;
            }
            if(diff == 1)
            {
                GraphEdges[i].push_back(j);
                GraphEdges[j].push_back(i);
            }
        }
    }
    int start = -1;
    int end = -1;
    // Find
    for(int i = 0 ; i < words.size(); i++)
    {
        if(words[i] == begin) start = i;
        if(words[i] == target) end = i;
    }
    
    vector<int> minDistArr = Dijkstra(start);
    if(minDistArr[end] == MAX_NUM) return 0;
    return minDistArr[end];
}