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

---

🔗 문제 링크

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

프로그래머스

---

반응형

728x90

👩‍💻 코드

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

using namespace std;

int diffCount(const string &str, const string &target){
    int count = 0;
    
    for(int i=0; i<target.size(); i++){
        if(str[i] != target[i]){
            count++;
        }
    }
    
    return count;
}

int solution(string begin, string target, vector<string> words) {
    if(find(words.begin(), words.end(), target) == words.end()){
        return 0;
    }
    
    vector<bool> visited(words.size(), false);
    queue<pair<string, int>> q;
    
    q.push({begin, 0});
    
    while(!q.empty()){
        auto f = q.front();
        string word = f.first;
        int count = f.second;
        
        if(word == target){
            return count;
        }
        
        q.pop();
        
        for(int i=0; i<words.size(); i++){
            if(diffCount(word, words[i]) == 1 && !visited[i]){
                q.push({words[i], count+1});
                visited[i] = true;
            }
        }
    }
    
    return 0;
}

---

📝 풀이

target이 words에 존재 하지 않은 경우의 예외 처리를 추가합니다.

이후 begin부터 시작하여 한 개의 다른 알파벳을 가지고 있는 단어를 찾습니다.

두 단어의 다른 알파벳 수를 구하는 diffCount 함수를 구현하여 활용합니다.

한 개의 다른 알파벳을 가지고 있고 아직 변환하지 않은 단어라면 q에 push 합니다.

BFS임으로 가장 먼저 q의 front의 단어가 target일 때 count를 return 합니다.

target을 찾지 못 하는 경우는 0을 return 합니다.