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

문제 링크: programmers.co.kr/learn/courses/30/lessons/43163

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

1. 주의할 점

- Map이나 배열을 통해 몇번 만에 Words에 있는 단어에 도착했는지 저장해야 한다

 

2. 구현

- DFS(현재 문자열, 바꾼 횟수)를 수행하며 DFS 함수 내에는 다음과 같은 조건들이 있다

- DFS() 함수의 가장 처음에는 현재 바꾼 횟수가 이미 구한 정답보다 많다면 Return한다

- 현재 문자열이 구하고자 하는 문자열과 같다면, Map의 2번째 인자인 Int값과 비교하여 더 적은 횟수로 도착했다면 갱신한다. 이후엔 Return

- 현재 문자열과 각 Words의 문자열을 비교하여 딱 1개가 차이난다면 해당 문자열이 이미 Map에 존재한다면 Map에 저장된 값>바꾼 횟수+1 이라면 갱신하고 그 문자열로 검사해본다. 만약 Map에 존재하지 않는다면 Map에 추가하고 해당 문자열로 DFS를 수행한다

- 만약 최종 문자열까지 도착하지 못한다면 0을 출력한다

 

#define MAX 987654321
#include <string>
#include <vector>
#include <map>
using namespace std;

map<string,int> m;
map<string,int> ::iterator it;
string result;
vector<string> v;
int ans = MAX;
void dfs(string str, int change){
    if(change >ans) return;
    if(str==result){
        if(change<ans){
            ans = change;
            m[str]=ans;
        }
        return;
    }
    for(int i=0;i<v.size();i++){
        string ss = v[i];
        int diff=0;
        for(int j=0;j<ss.size();j++)
            if(ss[j]!=str[j])
                diff++;
        if(diff==1){        //1개만 차이나는 경우
            it = m.find(ss);
            if(it==m.end()){      //아직 방문못해본 경우
                m[ss]=change+1;
                dfs(ss,change+1);
            }
            else{
                if(it->second>change+1){
                    m[ss]=change+1;
                    dfs(ss,change+1);
                }
            }
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    result=target;
    v=words;
    dfs(begin,0);
    if(ans==MAX) ans=0;
    answer=ans;
    return answer;
}