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

안녕하십니까. Eun🦆입니다.

풀이법 입니다.

 

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

#include <string>
#include <vector>
using namespace std;
int answer = 99;
void dfs(string begin, string target, vector<string> words, vector<bool> use, int cnt)
{
    // 매번 들어올 때마다 글자가 한 개 다른 문자를 찾는다.
    for(int i=0;i<words.size();i++)
    {
        int count = 0;
        for(int j=0;j<begin.length();j++)
        {
            if(use[i]==0 & begin[j]!=words[i][j])
                count++;
        }
        if(count==1)
        {
            if(words[i]==target & answer > cnt+1)
            {
                answer = cnt+1;
                return;
            }
            use[i] = 1;
            dfs(words[i], target, words, use, cnt+1);
            // 재귀로 dfs를 빠져나오면 해당 경우에서 다른 cnt가 1인 경우로 넘어가기 위해 use 초기화
            use[i] = 0;
        }
    }
}
int solution(string begin, string target, vector<string> words) {
    vector<bool> use(words.size(), 0);
    int cnt = 0;
    dfs(begin, target, words, use, cnt);
    if(answer == 99)
        return 0;
    return answer;
}

 

네이버 블로그 리뉴얼입니다.

(https://blog.naver.com/unsuk1/221996654979)