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

문제 링크

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

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

두 개의 단어 begin, target이 주어졌을 때, begin 단어를 변환해서 target 단어가 될 수 있는지 판별해보고 가능하다면 최소 몇단계를 거쳐야하는지 리턴하는 문제.

 

풀이

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.​

 단어를 변환할 수 있는 조건은 위와 같다.

 즉, 현재 단어를 now라고 했을 때 words에 있는 단어들 중에 now와 알파벳 하나만 다른 단어로 변환이 가능하다.

 DFS를 이용해서 문제를 풀었다.

 DFS의 깊이를 depth라고 했을 때 depth는 단어의 변환 횟수와 같다.

 그러므로 최대 깊이는 words.size()와 같다. depth와 words.size()가 같아졌다는 건 words에 있는 모든 단어들을 이용해서 변환을 했다는 뜻이다. 이때 우리는 2가지 경우를 생각해볼 수 있다.

1. 현재 단어에서 target으로 변환이 가능하다.

2. 현재 단어에서 target으로 변환이 불가능하다.

1번의 경우에는 depth가 최소 변환횟수인지 판별해서 answer값을 갱신해주고, 2번의 경우라면 그냥 리턴한다.

 

 만약 depth가 words.size()가 되기 전에 즉 words에 있는 모든 단어를 사용하지 않고도 target을 만들 수 있으면 이때의 변환횟수가 최소인지 판별하고 최소라면 answer값을 갱신한 뒤 리턴 아니면 그냥 리턴.

 그리고 이미 변환했던 단어로 굳이 다시 변환할 필요가 없다. 그래서 visited 배열을 만들어서 변환했던 단어로 다시 변환하는 것을 방지했다.

 

코드 작성

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_N = 50 + 5;
bool visited[MAX_N];
 
void backtracking(int depth, string now, string target, vector<string> words, int &answer){
    if(depth == words.size()){
        if(now == target){
            answer = min(answer,depth);
        }
        return;
    }
    if(now == target){
        answer = min(answer, depth);
        return;
    }
    for(int i = 0; i<words.size(); i++){
        int cnt = 0;
        for(int j = 0; j<words[i].length(); j++)
            if(now[j] != words[i][j])
                cnt++;
        if(cnt == 1 && !visited[i]){
            visited[i] = true;
            backtracking(depth + 1, words[i], target, words, answer);
            visited[i] = false;
        }
    }
}
int solution(string begin, string target, vector<string> words) {
    int answer = 100;
    backtracking(0, begin, target, words, answer);
    if(answer == 100)
        return 0;
    return answer;
}