[Programmers] 단어 변환

프로그래머스 - 단어 변환 문제입니다.

 

문제

BFS를 사용하여 시작 단어부터 문자가 단 1개 차이나는 단어를 depth를 늘려 추가해야겠다는 생각을 했습니다.

 

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

using namespace std;

class WordDepth {
    public:
    string word;
    int depth;
    
    WordDepth() {}
    WordDepth(string word, int depth) {
        this->word = word;
        this->depth = depth;
    }
};

int solution(string begin, string target, vector<string> words) {
    int i, j, differCnt = 0;
    bool check = false;
    vector<bool> wordCheckList(words.size(), false);	// 검사 했는지
    WordDepth preStr;	// 현재 비교중인 단어
    
    for(i = 0; i < words.size(); i++) {		// target 단어 존재 여부
        if(target == words[i]) {
            check = true;
            break;
        }
    }
    if(check == false) return 0;	// target 단어가 없을 경우 리턴
    
    queue<WordDepth> q;
    
    q.push(WordDepth(begin, 0));	// 시작 단어 큐에 추가
    while(!q.empty()) {
        preStr = q.front();		// 현재 비교 단어 큐에서 가져옴
        q.pop();
        for(i = 0; i < words.size(); i++) {
        	if(wordCheckList[i] == true) continue;	// 순환 방지
            for(j = 0; j < preStr.word.length(); j++) {
                if(preStr.word[j] != words[i][j]) differCnt++;
                if(differCnt > 1) break;
            }
            if(differCnt == 1) {
            	wordCheckList[i] = true;
            	q.push(WordDepth(words[i], preStr.depth + 1));	// 문자가 1개만 다를 경우 현재 비교 단어의 depth + 1 만큼 늘린 후 큐에 추가
            }
            if(differCnt == 1 && words[i] == target) return q.back().depth;		// 문자가 1개만 다르고 현재 문자가 target 과 같을 경우 정답
            differCnt = 0;
        }
    }
    return 0;	// target 단어가 있으나 변환 불가
}

단어와 depth를 저장할 수 있는 클래스 선언 후 시작 단어부터 문자가 1개만 다를 경우 depth를 현재 비교 중인 단어 depth + 1로 설정하고 큐에 저장합니다. 큐가 빌 때까지 수행하며, 큐가 비게 되면 변환할 수 없는 경우입니다.