프로그래머스: 단어변환

문제링크: https://programmers.co.kr/learn/courses/30/lessons/43163

프로그래머스

 

 문제설명 

 대상 단어(begin)를 목적단어(target)로 바꾸는것이 목표.

begin, target, 단어목록 이 주어지고 단어는 단어목록에 있는 단어로 한번에 하나씩 만 변경가능 

begin 단어가 target 단어로 변하는 최소값을 return

 

 

 알고리즘 

 

DFS를 이용하여 단어 목록에서 한글자 가 다른 경우를 찾아서 변환 ->변환->...-> 타겟 도착-> answer 업데이트 이방법  을 반복 

 

 코드 

 

#include<string>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int use[1000];
int answer = 1000;
 
 
void DFS(string begin, string target, vector<string>words, int count) {
 
    int len = begin.length();
    int size = words.size();
 
    for (int i = 0; i < size; i++) {
        //이미사용한 문자면은 SKIP
        if (use[i])continue;
 
        string word = words[i];
        int cnt = 0;
 
        //글자가 다른 갯수를 센다 .
        for (int j = 0; j < len; j++) {
            if (word[j] != begin[j])cnt++;
        }
 
        //단어가 한글자만 다르다면
        if (cnt == 1) {
 
            //단어 변환 끝
            if (word == target) {
                answer = min(count + 1, answer);
                return;
            }
 
            use[i] = 1;
            DFS(words[i], target, words, count + 1);
            use[i] = 0;//백트래킹
 
        }
    }
}
 
 
int solution(string begin, string target, vector<string> words) {
    DFS(begin, target, words, 0);
    if (answer == 1000) return 0;
    return answer;
}