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

 

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

 

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

프로그래머스

---

 

 

해결전략

 

깊이우선탐색 DFS

 

---

 

 

정답코드

 

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
 
int answer = 987654321;
int n; 	 // 단어의 개수
int len; // 단어의 길이
vector<int> ch; // 각 단어의 방문 여부를 저장할 벡터
 
bool canChange(const string& str1, const string& str2) // 두 문자열이 한 글자만 다른지 확인하는 함수
{
    int diffCount = 0; // 다른 글자 수를 카운팅하는 변수
    
    for (int i = 0; i < str1.size(); i++) 
    {
        if (str1[i] != str2[i]) {
            diffCount++; // 글자가 다르다면 ++
        }
        if (diffCount > 1) {
            return false; // 두 글자 이상 다른 경우 false 반환
        }
    }
    
    return diffCount == 1; // 한 글자만 다른 경우 true 반환
}
 
void DFS(string str, const string& target, const vector<string>& words, int cnt)
{    
    if (str == target){ // 현재 문자열이 목표 문자열과 같은 경우
        answer = min(answer, cnt);
        return;
    }
    
    for (int i = 0; i < n; i++) // 모든 단어를 탐색
    {
        if (ch[i] == 0 && canChange(str, words[i])) // 방문X && 현재 단어와 한 글자만 다른 경우
        {
            ch[i] = 1;
            DFS(words[i], target, words, cnt + 1);
            ch[i] = 0;
        }
    }
}
 
int solution(string begin, string target, vector<string> words) {
    len = begin.size();
    n = words.size();
    ch.resize(n);
    
    DFS(begin, target, words, 0);
    
    answer = answer == 987654321 ? 0 : answer;
    
    return answer;
}
 
int main() {
    string begin = "hit";
    string target = "cog";
    vector<string> words = {"hot", "dot", "dog", "lot", "log", "cog"};
 
    int result = solution(begin, target, words);
    cout << result << endl;
 
    return 0;
}

 

 

---