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

문제

프로그래머스

 

주어진 시작 단어를 목표 단어로 변환하는데, 매번 한 글자씩만 바꿀 수 있으며, 중간 과정은 주어진 단어 목록 내에서만 가능할 때, 최소 변환 단계를 구하는 문제이다.

---

풀이

1. target 단어가 words 안에 있는지 확인한다.
2. target 단어가 있다면 BFS를 이용하여 target 단어까지의 최소 변환 단계를 구한다. 

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

using namespace std;

pair<bool,int> visited [50];

bool IsTransitionWord(string curWord, string target){
    int match = 0;
    for(int i = 0; i< curWord.length(); i++){
        if(curWord[i] == target[i])
            match++;
    }
    
    return match == curWord.length() - 1; 
}

int BFS(string begin, string target, vector<string> words){
    int n =words.size() ,m = words[0].size(), count = 1;
    queue<int> q;
    
    for(int i = 0; i < n; i++){
        if(IsTransitionWord(begin, words[i]))
        {
            visited[i].first = true;
            visited[i].second = 1;
            q.push(i);
        }
    }
    
    while(!q.empty()){
        int wordNum = q.front();
        
        if(words[wordNum] == target){
            
            return visited[wordNum].second;
        }
        q.pop();
        
        for(int i = 0; i< n; i++){
            
            if(!visited[i].first && IsTransitionWord(words[wordNum], words[i])){
                visited[i].first = true;
                visited[i].second = visited[wordNum].second + 1;
                q.push(i);
            }
        }
    }
}

int solution(string begin, string target, vector<string> words) {

    for(int i = 0; i < words.size(); i++){
        if(target == words[i])
            break;
        
        if(i == words.size() - 1)
            return 0;
    }
    
    return  BFS(begin, target, words);
}