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

bfs로 풀 수 있다.

큐를 만든 다음에 문자열을 넣는다. 그리고 모든 words에 대해서 차이가 1이 나는 것을 넣는다. visited 배열을 선언해줘서 중복 방문을 방지한다.

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

using namespace std;

struct word{
    string s;
    int cnt;
};

int visited[101];

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    queue<word> q;
    q.push({begin, 0});
    while (!q.empty()){
        string t = q.front().s;
        int num = q.front().cnt;
        q.pop();
        if (t==target){
            answer = num;
            break;
        }
        for (int i=0;i<words.size();i++){
            int dif = 0;
            if (visited[i]==1) continue;
            for (int j=0;j<t.size();j++){
                if (t[j]!=words[i][j]){
                    dif++;
                }
                if (dif>1) { 
                    break;
                }
            }
            if (dif==1){
                visited[i]=1;
                q.push({words[i], num+1});
            }
        }
    }
    return answer;
}