[프로그래머스] 단어변환 (Lv3)

programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환

C++

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int answer = 100;
int check[50];

int dif(string pre_word, string check_word) {
    int cnt=0;
    for(int i=0;i<pre_word.size();i++){
        if(pre_word[i]!=check_word[i]) cnt++;
    }
    return cnt;
}

void DFS(string begin, string target, vector<string> words, int time) {
    for(int i=0;i<words.size();i++) {
        if(check[i]==1) continue;
        if(dif(begin,words[i])==1){
            if(words[i]==target) {answer=min(answer,time+1); return;}
            else {
                check[i]=1;
                DFS(words[i],target,words,time+1);
                check[i]=0;
            }
        }
    }
}

int solution(string begin, string target, vector<string> words) {
//     words에 target 값 유무 check
    int c=0;
    for(int i=0;i<words.size();i++){
        if(words[i]==target) c=1;
    }
    if(c==0) return 0;
    
    DFS(begin, target, words, 0);
    if(answer==100) answer=0;
    return answer;
}

 

let check=[];
let answer=100;

function dif(a,b){
    let cnt=0;
    for(let i=0;i<a.length;i++){
        if(a[i]!==b[i]) cnt+=1;
    }
    return cnt;
}

function dfs(begin,target,words,time) {
    for(let i=0;i<words.length;i++){
        if(check[i]===1) continue;
        if(dif(begin,words[i])===1){
            if(words[i]===target){
                answer = answer<time+1 ? answer : time+1;
                return;
            }
            check[i]=1;
            dfs(words[i],target,words,time+1);
            check[i]=0;
        }
    }
}

function solution(begin, target, words) {
    if(words.includes(target)===false){
        return 0;
    }
    dfs(begin,target,words,0);
    if(answer===100) return 0;
    return answer;
}