[프로그래머스] level 3 - 단어 변환

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

프로그래머스

본 문제는 프로그래머스 level 3 문제로 DFS 문제다. 개인적인 생각으론 프로그래머스는 BFS 보다 DFS를 이용하여 풀었을 때 코드가 간결하고 쉽게 풀리는거 같다. 최단 거리를 구하는 문제는 BFS를 사용하는게 빠르지만 이 문제는 DFS를 이용하였고 target에 도착할 때 마다 값을 비교하여 최솟값을 구하였다.

자세한 설명은 주석처리 하였다.

#include <string>
#include <vector>
 
using namespace std;
 
// 문제에서 words의 길이가 최대 50이므로 50이하의 정답이 나온다. 
int ans = 50;
 
void dfs(string start, string target, vector<string> words, vector<bool> chk, int cnt) {
    // target에 도착하였을 경우 최솟값 비교
    if (start == target) {
        if (ans > cnt) ans = cnt;
        return;
    }
    for (int i = 0; i < words.size(); i++) {
        if (chk[i]) continue;
        int count = 0;
        for (int j = 0; j < start.size(); j++) {
            if (start[j] == words[i][j]) count += 1;
        }
        // 글자가 1개 차이날 경우 DFS
        if (count == start.size()-1) {
            chk[i] = true;
            dfs(words[i], target, words, chk, cnt + 1);
        }
    }
}
 
int solution(string begin, string target, vector<string> words) {
    // target이 words에 없는 경우 확인하기
    bool flag = false;
    for (int i = 0; i < words.size(); i++) {
       if (target == words[i]) flag = true; 
    }
    if (!flag) return 0;
    else {
        vector<bool> chk(words.size(), false);
        dfs(begin, target, words, chk, 0);
        return ans;
    }
}