프로그래머스 - 단어변환 - Level 3

문제

풀이전략

1. 한번에 한단어만 바꿀 수 있다. 따라서 바꾸기가 가능한지 아닌지에 대한 함수를 만든다.
2. 바꾼 글자가 중복되면 안되기때문에 ch배열을 만들어준다.
3. 횟수가 중요하기 때문에 BFS를 사용한다.
4. 횟수까지 저장할 수 있는 structure를 만들어서 queue에 넣어 사용한다.

코드

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

struct myWord{
    //해당 단어와 값을 저장한 구조체이다. 
    string word;
    int val;
    myWord(string a, int b){
        word = a;
        val = b;
    }
};

// 글자를 바꿀 수 있는지 없는지에 대한 함수이다. 
bool isChangable(string before, string after){
    int cnt = 0;

    for(int i=0; i<before.length(); i++){
        if(before[i] != after[i]) cnt++;
        if(cnt>1) return false;
    }
    // 서로 다른글자가 1글자라면 true
    // 그렇지 않다면 false이다. 
    if(cnt == 1) return true;
    return false;
}
// 중복된 글자로 가기 않기 위한 체크배열 
bool ch[51];

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    
    queue<myWord> q;
    // 시작하는 단어를 넣는다.
    q.push(myWord(begin, 0));
    while(!q.empty()){
        myWord ret = q.front();
        q.pop();
        // 타겟단어이면 answer에 그 val을 넣고 종료한다. 
        if(ret.word == target){
            answer = ret.val;
            break;
        }
        // 바꿀수 있는 단어들을 계속 찾으며 큐에 넣어준다. 
        for(int i=0; i<words.size(); i++){
            if(!ch[i] && isChangable(ret.word, words[i])){
                ch[i] = true;
                q.push(myWord(words[i],ret.val+1));
            }
        }
    }
    
    return answer;
}

소감

전형적인 BFS문제이다. String과 BFS를 같이 조합해서 푸는게 흥미로웠다. 문제는 쉽지만 개념적으로 중요한 문제이다.