[프로그래머스] 3단계 - 단어 변환

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 변환할 수 있는지 return

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

프로그래머스

 

문제 풀이법

dfs로 풀 수 있는 문제이다

한 번에 한 개의 알파벳만 바꿀 수 있다는 문구가 핵심이다

 

우선 dfs를 돌기 전에 words에서 target 단어가 있는지 검사 해주었다

없으면 변환할 수 없으므로 바로 0을 return 해주었다

 

dfs를 도는데 매개변수는 현재 문자열인 string str, 변환할 문자열인 string target, 단어 집합인 words, 현재 몇 단계의 과정인지 나타내는 int n이 있다

dfs의 탈출 조건은 현재 문자열인 str과 변환할 문자열인 target이 같을 때 이다

이때 최소의 수를 return 해야하기에 min을 사용하여 최소값으로 갱신해주었다

 

이제 words를 돌면서 변환할 문자열을 찾아야 한다

현재 문자열과 바꿀 문자열에서 다른 알파벳이 1개만 있는지 검사한다

물론 이미 탐색한 문자열이면 검사하지 않는다

다른 알파벳이 1개만 있는 문자열이라면 따로 벡터에 저장해둔다

 

words를 다 돌고나면, 다른 알파벳이 1개만 있는 words의 인덱스를 담은 벡터를 돌면서 dfs를 수행해준다

 

예를 들자면 begin이 "hit"이고 target이 "cog"이고, words가 ["hot", "dot", "dog, "lot", "log", "cog"]라면, hit에서 알파벳이 1개만 다른 것은 ["hot"] 이므로 "hot"을 begin으로 하여 다시 dfs를 돈다

이젠 begin이 "hot"이므로 hot과 알파벳이 1개만 다른 것은 hit을 제외하고 ["dot", "lot"]이다 

그럼 먼저 "dot"을 begin으로 하여 다시 dfs 돌고, target을 찾을 때 까지 돌고 오면, "lot"을 begin으로 하여 다시 dfs를 도는 방식이다 

 

 

 

소스 코드

#include <string>
#include <vector>

using namespace std;

int visited[51] = { 0 };
int answer = 100000;

void dfs(string str, string target, vector<string> words, int n) {
    
    if (str == target) {
        answer = min(answer, n);
        return ;
    }
    
    vector<int> v_idx;
    for (int i = 0; i < words.size(); i++) {
        if (visited[i] == 1)
            continue;
        
        int diff = 0;
        for (int j = 0; j < words[i].size(); j++) {
            if (words[i][j] != str[j])
                diff++;
        }
        
        if (diff == 1)
            v_idx.push_back(i);
    }
    
    for (int i = 0; i < v_idx.size(); i++) {
        visited[v_idx[i]] = 1;
        dfs(words[v_idx[i]], target, words, n + 1);
        visited[v_idx[i]] = 0;
    }
    
    
}


int solution(string begin, string target, vector<string> words) {
    
    bool flag = false;
    
    for (int i = 0; i < words.size(); i++) {
        if (words[i] == target) {
            flag = true;
            break;
        }
    }
    
    if (flag == false)
        return 0;
    
    dfs(begin, target, words, 0);
    return answer;
}