[C++] 단어 변환

[문제]

코딩테스트 연습 - 단어 변환 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[문제 풀이]

요구사항이 좀 있어서 어려워 보일 수 있지만 하나씩 차근차근 해보면 생각보다 쉽게 풀린는 문제였다.

우선 첫번째로 oneCheck 라는 함수를 만들어서 알파벳이 1개만 다른지 아닌지 확인을 하는 bool형태의 함수를 만들었다.

두번째로는 bfs를 이용해서 begin부터 시작해서 words의 단어들을 확인해보는 함수를 만들었다.

세번째로 bfs를 이용할때 한번이라도 단어를 선택했던 단어는 중복처리를 없애기 위해서 사용을 했었는지 아닌지 visited배열을 이용해서 확인을 하였다.

[코드]

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

using namespace std;

bool visited[51];

bool oneCheck(string begin, string target){
    
    int flag = 0;
    
    for(int i = 0;i<target.size();i++){
        if(begin[i] != target[i]){
            flag++;
        }
    }
    
    if(flag == 1){
        return true;
    }    
    return false;
}

int bfs(string begin_words, string target, vector<string> words){
    
    //1개만 다른지 아닌지 flag를 통해서 확인.
    //visited를 통해서 이미 왔었는지 아닌지 확인.
    
    queue<pair<string,int > > alpha;
    alpha.push(make_pair(begin_words,0));
    
    while(alpha.size() > 0){
        //큐의 가장 첫번째 단어 가져오기.
        string curS = alpha.front().first;
        int curCount = alpha.front().second;
        //가져왔으면 해당 단어를 큐에서 제거하기.
        alpha.pop();
                
        if(curS == target){
            return curCount;
        }
        
        for(int i = 0;i<words.size();i++){
            //만일 아직 방문하지 않은 단어라면
            if(visited[i] == 0 ){
                //방문표시
                //1개만 다른지 아닌지 확인해보기
                bool checked;
                checked = oneCheck(curS, words[i]);
                //만일 1개만 다른게 맞다면
                if(checked == true){
                    //queue에 넣어주기.
                    visited[i] = 1;
                    alpha.push(make_pair(words[i], curCount + 1));
                }
            }
        }
    }
    
    return 0;
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    
    answer = bfs(begin, target, words);
    
    return answer;
}