단어변환

문제 설명

입출력 예

begin                 target                 words                                                                                                                              return

"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

 

 

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


using namespace std;
vector<bool> wordCheck(51,false);
vector<string> wordsBook;
int answer =100000;
string targetWord;

bool compare(string begin, string word)//비교 후 움직일 수 있으면 true, 아니면 false
{   
    /////cout <<"begin : "<<begin<<"비교할 word : "<<word <<'\n';
    bool check = false;
    int limit = begin.size();
    int correct=0;
    for(int i=0; i<limit; i++)
    {
        if(begin[i] == word[i])correct++;
    }
    if(correct == (limit-1)) check = true;
       
     return check;
}
    

    
void DFS(string begin,int cnt)
{
    if(begin == targetWord)
    {
        answer = min(answer, cnt);
        return;
    }
    if(cnt > 100) return;

    for(int i =0; i<wordsBook.size(); i++)
    {
        if(!wordCheck[i] && compare(begin, wordsBook[i]))
        {
        wordCheck[i]=true; 
        DFS(wordsBook[i], cnt+1 );
        wordCheck[i] = false;    
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    targetWord = target;
    bool check = false;
    wordsBook= words;
    for(int i=0; i<words.size(); i++)
    {
        if(target == words[i]) 
        {
            check=true;
            break;
        }
    }
    if(!check) {answer=0;return answer;}  
   
    DFS(begin, 0);
    
    return answer;
}

=> 학부시절 풀었던 문제와 똑같은 문제입니다. (배XX교수님의 자료구조시간이었습니다.) 

 

=> 기존 개념은 DFS를 사용하는 것입니다. 

 

=> 현재 BEGIN단어를 이동시켜가며 TARGET단어를 마주칠 때까지 횟수를 구하고, 최소 횟수를 구하는 알고리즘입니다. 

 

=> 현재단어에서 다른 단어로 갈 수 있는 조건을 compare함수를 생성하여 구현하였습니다. 

 

=> compare함수를 DFS를 시작하는 조건문에 넣어 TRUE값을 반환한 단어에만 갈 수 있도록 표현하였습니다. 

 

=> 이 방안 말고도 메인(Solution)문 시작 전에 모든 단어에 대한 EDGES를 구현하여 begin단어에서 갈 수 있는 단어들을 미리 표현해두는 방법도 있습니다. 

 

https://codingham.tistory.com/155

백준 1260 -DFS와 BFS

 

=> 해당방안은 위의 포스팅을 참조하면 구성할 수 있습니다.(시간이 날 때 구현해보도록 하겠습니다.)