[プログラマー/C++]ワード変換

📓 https://programmers.co.kr/learn/courses/30/lessons/43163

📓 問題を解く

⏱ 25'枝を伸ばしたつもりでDFSで解いた質問の種類はDFS/BFSと書いてあるので、近づきやすいです.プログラマーはいつでもstringを使用します.よくat(i)を使うようです.ㅎ…

開始語としてdfsを用い、現在stringがtargetになった場合、出力level(=depth)が最小となる.
したがって、dfsの関数因子には、현재 stringおよびlevelが必要である.
(wordsとtargetをパラメータとして一緒に置き,プログラマー形式で解く.

💡 重要なのは、すでに書いた単語を書き換えることができるようにすれば、タイムアウトして、必ずbool visitedを使って並べ替えなければなりません!

💡また、一度にtargetに到着して終了するのではなく、複数のパスの中で最短レベルが現れるように選択するのでbacktracking後はvisited=falseに変更します.

dfsで、延長する単語を選択するには、まずパスします.
指定されたwords配列を回転させ、まだアクセスされていない文字列を見つけます.
今stringは1つ1つと比較して、他の字数は1つの時です!その字で呼び直せばいいです(もちろんlevelを1つ増やします).

cppで文字列を単語ごとに比較する場合はstr.at(i)関数を使用します!

コード#コード#

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

using namespace std;
int answer = 2147000000;
bool visited[51];

void dfs(string str, int L, string target, vector<string> words){
    
    if(str==target){
        answer=min(answer,L);
        return;
    }
    
    for(int i=0;i<words.size();i++){
        
        if(visited[i]) continue;
        
        string str2=words[i]; //비교할 단어
        
        int cnt=0;
        //한 글자씩 비교해보기
        for(int j=0;j<str.size();j++){
            if(str2.at(j)!=str.at(j)) cnt++;
        }
        //다른 글자가 1개라면 해당 글자로 가지 뻗기
        if(cnt==1){
            visited[i]=true;
            dfs(str2, L+1, target, words);
            visited[i]=false;
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    
    //target이 words안에 있나
    bool found=false;
    for(int i=0;i<words.size();i++){
        if(target==words[i]){
            found=true;
            break;
        }
    }
    
    if(!found) return 0;
    
    dfs(begin, 0, target, words);
    return answer;
}