[Programmers] 단어 변환 (C++)

문제

두 개의 단어 begin, target과 단어의 집합 words가 주어진다.

아래의 규칙으로 begin에서 target으로 변환하는 가장 짧은 변환 과정 찾기

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

예시 )

begin : “hit”

target : “cog”

words : ["hot","dot","dog","lot","log","cog"]

변환 과정 : "hit" -> "hot" -> "dot" -> "dog" -> "cog”

생각할 것

백트래킹을 사용해서 모든 경우를 탐색

발견한 최소 탐색거리보다 크면 더 이상 탐색을 진행하지 않음

단어가 하나만 다른지 체크

코드

#include <string>
#include <vector>
#include <iostream>
#include <limits.h>

using namespace std;

vector<bool> visited;
int res = INT_MAX;

bool diffOne(string begin, string target) { 
    int diff = 0;
    for(int i=0; i<begin.size(); i++){
        if(begin[i] != target[i]) diff++;
        if(diff > 1) return false;
    }
    return true;
}

void dfs(string begin, string target, vector<string> words, int count){
    if(res <= count) return;
    if(begin == target) {
        res = min(res, count);
        return;
    }
    
    for(int i=0; i<words.size(); i++){
        if(visited[i]) continue;  // 이미 확인 한 단어인지 체크
        visited[i] = true;       
        if(diffOne(begin, words[i])) {  // 한 개의 문자만 다른지 체크
            dfs(words[i], target, words, count+1);
        }
        visited[i] = false;
    }
    
    return;
}

int solution(string begin, string target, vector<string> words) {
    visited.assign(words.size(), false);
    dfs(begin, target, words, 0);
    
    if(res == INT_MAX) return 0;
    else return res;
}