단어 변환

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

 

• 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
• words에 있는 단어로만 변환할 수 있습니다.
• 예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

 

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

begin	target	words	return
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

---

문제 해설

아주 간단한 DFS문제이다.

쉽게 생각해서, 각 문자당 해당사항이 있는지, 이 해당사항이 어떻게 해당되는지를 이해하면 되는데, 이는 다음과 같다.

 

모든 문자는 한번씩 밖에 바꾸지 못한다.

(단어의 스펠링마다 하나씩 체크를 해줘야한다는 뜻)

모든 문자는 words배열 안의 문자끼리만 교환이 가능하다.

(모든 단어는 words배열안에서 체크해야한다는 뜻임으로 for문형태로 전체순환을 돌려준다.)

---

첫 번째 시도

#include <string>
#include <vector>
#include <set>

using namespace std;

set<int> Scount;

void DFS(string input, string& target, vector<string>& words, vector<bool> visited, int count = 0) {
    if(input == target)
    {
        Scount.insert(count);
        return;
    }
        
    for(int i = 0; i < words.size(); i++) 
    {
        if(visited[i] == false)
        {
            int chack = 0;
            for(int j = 0; j < input.size(); j++) 
            {
                if(input[j] != words[i][j]) chack++;
                if(chack > 1) break;
            }
            if(chack == 1) 
            {
                vector<bool> newvisit(visited);
                newvisit[i] = true;
                DFS(words[i], target, words, newvisit, count + 1);
            }
        }
    }
}
int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    vector<bool> visited;
    visited.resize(words.size());
    DFS(begin, target, words, visited);
    return Scount.size() > 0 ? *Scount.begin() : 0;
}

성공

모든 해당되는 조건을 if문으로 조절했다.

string문 조건연산은 대부분 if문을 이용해야한다는게 참 안타깝다.