(c++)프로그래머스 코딩테스트 연습 - 단어 변환

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

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

[풀이]

dfs로 words배열에서 현재 단어와 한글자만 다른 단어를 찾아 현재 단어가 target단어가 될 때까지 탐색하는 방법으로 풀었다.

단계가 현재까지 구한 최솟값보다 커질 경우 가지치기 하여 시간을 단축하였다.

 

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

using namespace std;

vector<string>Words;
int word_cnt;
bool check[50];
int Min=987654321;

bool Diff(string a, string b){
    int cnt=0;
    for(int i=0;i<a.size();i++){
        if(a[i]!=b[i])
            cnt++;
        if(cnt>1)
            return false;
    }
    return true;
}

void dfs(string curWord, string target, int cnt){
    if(cnt>=Min)
        return;
    if(curWord==target){
        Min=cnt;
        return;
    }
    for(int i=0;i<word_cnt;i++){
        if(check[i]==true)
            continue;
        if(Diff(curWord, Words[i])){
            check[i]=true;
            dfs(Words[i],target,cnt+1);
            check[i]=false;
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    Words=words;
    word_cnt=words.size();
    dfs(begin,target,0);
    
    if(Min==987654321)
        Min=0;
    return Min;
}