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

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

출처: 프로그래머스

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

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int answer = 50;
bool visited[50]; //방문words

//begin과 한 글자만 다른 words 찾는 함수
bool oneDiff(string a, string b){
    int cnt_diff = 0;
    for(int i=0; i<b.size(); i++){
        if(a[i]!=b[i]){
            cnt_diff ++;
        }
    }
    if(cnt_diff == 1) //하나만 다르면
        return true;
    else
        return false;
}

void dfs(string begin, string target, vector<string> words, int idx){
   
    if(begin == target){ //종료조건
        answer = min(idx, answer);
        return; //종료
    }
    
    for(int i=0; i<words.size(); i++){
        //한글자만 다르고 아직 방문하지 않았으면
        if(oneDiff(begin, words[i]) && !visited[i]){
            visited[i] = true;
            dfs(words[i], target, words, idx+1);
            visited[i] = false; //dfs종료 후 돌아오면, 백트래킹
        }
    }
    return;
}

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

    dfs(begin, target, words,0);
    if(answer == 50){ //변환할 수 없으면 0
        answer = 0;
    }
    return answer;
}

최대 words의 길이가 50이니까 answer도 50, visited크기도 50으로 맞춘다.

이 말은 최대로 50번 변환할 수 있다는 것이다.

우리는 최단 횟수를 구해야 하기에 횟수 0부터 시작해서 50이랑 비교해서 최솟값을 구해낸다.

 

dfs로 풀이했다.

begin과 words에 있는 단어를 비교했을 때, 한 글자만 다른 단어만 방문 가능하다.

한 글자만 다른 것을 판별하는 함수를 따로 oneDiff()로 만들었다.

 

아직 방문하지 않았고 한 글자만 다른 단어만 방문 표시하고 다음 단계인 dfs 진행한다.

dfs가 종료되었을 때, 다시 백트래킹으로 visited [i]= true 했던 것을 visited[i] = false 처리해준다.

---

백트래킹...............

연습하자