[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 합니다.

입출력 예

begin	target	words	return
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

풀이

단어의 길이가 10이하이고,

총 단어의 개수는 50개 이하이므로 시간복잡도가 널널하다고 생각했다.

 

BFS방식으로 풀이했으며,

words 길이만큼 visited 배열을 만들어 이용했다.

 

문제는 길었지만, 꼬지 않은? 문제여서 정형화된 풀이로 풀 수 있었다.

코드 

#include <string>
#include <vector>
#include <queue>

using namespace std;
bool isCanConvert(string begin, string target) {
    int count = 0;
    for(int i=0;i<begin.size();i++) 
        if (begin[i] != target[i]) count++;
    return count <= 1;
}
int BFS(string begin, string target, vector<string> words) {
    vector<bool> visited(words.size());
    queue<pair<string, int>> q;
    q.push({begin, 0});
    
    while(!q.empty()) {
        string temp = q.front().first;
        int count = q.front().second;
        q.pop();
        
        for(int i=0; i<words.size();i++) {
            if (visited[i]) continue;
            if (!isCanConvert(temp, words[i])) continue;
            if (words[i] == target) return count + 1;
            
            visited[i] = 1;
            q.push({words[i], count + 1});
        }
    }
    return 0;
    
}
int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    answer = BFS(begin, target, words);
    return answer;
}

결과