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

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

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

단어 변환

문제

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

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

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

 

 

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

 

풀이

입출력 예시

 

풀이

한 글자만 다른 단어를 찾아 그 단어로 변환하는 과정을 target이 될 때 까지 반복해야한다.

 

주의해야할 점으로는 단어 길이가 3이상 10이하라는 점과, 변환하는 단계가 최소가 되도록 해야한다는 점이 있다. 이를 위해서 DFS(또는 BFS)를 진행하면서 값이 더 작은 쪽으로 계속 갱신해주는 과정이 필요하다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool is_dif(string a, string b) {
    int count = 0;
    int a_len = a.length();

    for (int i = 0; i < a_len; i++) {
        if (a[i] == b[i]) {
            count++;
        }
    }

    if (count == a_len - 1) {
        return true;
    }
    else {
        return false;
    }
}

int DFS(string begin, string target, vector<bool> visited, int w_size, vector<string> words) {
    int count = 999999;

    if (begin == target) {
        return 1;
    }

    for (int i = 0; i < w_size; i++) {
        if (is_dif(begin, words[i]) && visited[i] == false) {
            visited[i] = true;
            // 변환한 횟수가 더 작은 값을 저장
            count = min(count, 1 + DFS(words[i], target, visited, w_size, words));
            visited[i] = false;
        }
    }

    return count;
}

int solution(string begin, string target, vector<string> words) {
    int answer = 999999;
    vector<bool> visited(words.size(), false);
    int w_size = words.size();

    if (find(words.begin(), words.end(), target) == words.end()) {
        return 0;
    }

    for (int i = 0; i < w_size; i++) {
        if (is_dif(begin, words[i])) {
            visited[i] = true;
            answer = min(answer, DFS(words[i], target, visited, w_size, words));
            visited[i] = false;
        }
    }

    return answer;
}