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

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

📓 문제풀이

⏱ 25'
가지를 뻗어 나가는 거로 생각하고 DFS로 풀었다. 문제 종류에 DFS/BFS라고 써있어서 접근이 쉬웠던 거 같다. 언제나 프로그래머스에서는 string.at(i)을 많이 쓰는 거 같ㄷ.ㅏ...

• 시작 단어로부터 dfs 를 이용해 가지를 뻗어나가고, 현재 string이 target과 같아지는 경우 중에 level(=depth)이 가장 적은 것을 출력한다.
  따라서 dfs함수 인자에는 현재 string과 level이 꼭 필요하다.
  (words와 target은 프로그래머스 solution 형태로 풀기 위해 인자로 넣어주었다.)

• 💡 중요한 건 이미 쓴 단어를 다시 쓸 수 있게 냅두면 시간초과가 되니깐 꼭 bool visited배열을 이용해줘야 한다!

• 💡그리고 한 번 target 도달한다고 해서 끝나는 게 아니라 여러 경로 중 최단레벨이 나오는 것을 골라야하므로 백트래킹 후에 visited=false로 바꿔줘야한다.

• dfs 내에서 뻗어나갈 단어를 고르는 것은 일단 다 돌려보야 한다.
  주어진 words 배열을 돌리면서, 아직 방문하지 않은 string을 찾아내고,
  현재 string 과 한글자씩 비교해가며 다른 글자수가 1개일 때! 그 글자로 재귀호출 해주면 된다 (당연히 level을 하나 늘린다.)

• cpp에서 string을 한 글자씩 비교할 땐 str.at(i) 함수 이용!

코드

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

using namespace std;
int answer = 2147000000;
bool visited[51];

void dfs(string str, int L, string target, vector<string> words){
    
    if(str==target){
        answer=min(answer,L);
        return;
    }
    
    for(int i=0;i<words.size();i++){
        
        if(visited[i]) continue;
        
        string str2=words[i]; //비교할 단어
        
        int cnt=0;
        //한 글자씩 비교해보기
        for(int j=0;j<str.size();j++){
            if(str2.at(j)!=str.at(j)) cnt++;
        }
        //다른 글자가 1개라면 해당 글자로 가지 뻗기
        if(cnt==1){
            visited[i]=true;
            dfs(str2, L+1, target, words);
            visited[i]=false;
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    
    //target이 words안에 있나
    bool found=false;
    for(int i=0;i<words.size();i++){
        if(target==words[i]){
            found=true;
            break;
        }
    }
    
    if(!found) return 0;
    
    dfs(begin, 0, target, words);
    return answer;
}