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

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

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

코드 설명

cnt 변수를 이용하여 한 글자가 다른 걸 찾는다 -> 재귀

재귀를 돌면서 target과 일치한다면 그때까지의 level을 tmp 변수에 담아둬서 가장 빠른 과정으로 도착할 경우를 찾는다.

(이때 min을 쓸거면 초기 result값을 큰 값으로 지정해둬야 한다!!! 여기서 실수해서 디버깅함...)

또한 result가 변화없이 다시 main으로 돌아왔다면 target을 한 번도 만나지 않았다는 의미 이므로 0을 반환해준다.

 

 

코드

#include <string>
#include <vector>
#include <iostream>
using namespace std;
bool visited[51];
int tmp;
int result=999;
int cnt;
void dfs(int level, string& begin, string& target, vector<string>& words) {
    if (begin == target) {
        tmp = level;
        result = min(tmp, result);

        return;
    }




    for (int i = 0; i < words.size(); i++) {
        if (!visited[i]) {
            cnt = 0;
            for (int j = 0; j < words[i].size(); j++) {
                if (words[i][j] != begin[j]) {
                    cnt++;
                }
            }
            if (cnt == 1) {
                visited[i] = true;
                cout << words[i] << " ";
                dfs(level + 1, words[i], target, words);
                visited[i] = false;
            }
        }

    }


}
int solution(string begin, string target, vector<string> words) {
    int answer = 0;

    dfs(0, begin, target, words);



    if (result == 0) answer = 0;
    else {
        answer = result;
    }

    return answer;
}
int main() {

    solution("hit", "cog", { "hot", "dot", "dog", "lot", "log", "cog" });

    return 0;
}