[프로그래머스 lv3] 단어 변환 풀이

해설

재귀를 이용하여 가능한 모든 경우를 탐색하는 백트래킹 문제이다.

현재 단어를 x라고 했을 때, 다음으로 이동할 수 있는 단어는 words에 있는 단어 중 아직 방문하지 않았고, x와 한개의 글자만 다른 단어이다.

다음 단어로 이동하면서, 도착한 노드가 target과 같을 때 이동 횟수의 최솟값을 갱신한다.

모든 경로를 탐색한 뒤 이동 횟수의 최솟값을 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

int mn = 100;
vector<bool> visited(55, false);

bool check(string a, string b) {

    int cnt = 0;
    for (int i=0; i<a.size(); i++) {
        if (a[i] != b[i]) cnt++;
    }
    return (cnt == 1);
}

void func(string x, int cnt, string target, const vector<string>& words) {

    if (x == target) {
        mn = min(mn, cnt);
        return ;
    }

    for (int i=0; i<words.size(); i++) {
        if (visited[i] || !check(x, words[i])) continue;
        visited[i] = true;
        func(words[i], cnt+1, target, words);
        visited[i] = false;
    }
}

int solution(string begin, string target, vector<string> words) {

    func(begin, 0, target, words);
    if (mn == 100) return 0;
    return mn;
}