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

단어 변환

---

1. 이해하기

• begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾는 것이다.
  1. 한 번에 한 개의 알파벳만 바꿀 수 있다.
  2. words에 있는 단어로만 변환할 수 있다.
• dfs를 이용하여 찾을 수 있다.

---

2. 구현하기

• dfs함수를 만든다.

  • dfs(now,target,depth,visited,words): 현재와 target을 비교해서 같으면 최소 과정을 반환해준다. 현재까지 찾은 과정보다 더 많은 과정을 찾으려고 하는 경우에는 바로 끝나도록 해준다.
  • 있는 단어들을 모두 살펴보면서 이미 지나온 경우는 패스할 수 있도록 visited를 이용한다. 또한 고른 단어와 현재 단어가 한글자만 다른지 확인하고 맞다면 dfs를 반복한다.

  void dfs(string now, string target, int depth, vector<bool>& visited, vector<string>& words) {
      if(ans < depth) return;
      if(now == target) {
          ans = min(ans,depth);
          return;
      }
  
      for(int i = 0; i < words.size(); i++) {
          if(visited[i]) continue;
          int cnt = 0;
          for(int j = 0; j < words[i].size(); j++) {
              if(now[j] != words[i][j]) cnt++;
          }
          if(cnt == 1) {
              visited[i] = true;
              dfs(words[i],target,depth+1,visited,words);
              visited[i] = false;
          }
      }
  }

• words안에 찾고자 하는 단어가 없다면 0을 리턴한다. 또한 바꾸는 방법이 없을 경우에도 0을 리턴한다.

  int solution(string begin, string target, vector<string> words) {
      int answer = 0;
      bool found = false;
      for(int i = 0; i < words.size(); i++) {
          if(words[i] == target) found = true;
      }
      if(!found) return 0;
      vector<bool> visited(words.size(),false);
      dfs(begin,target,0,visited,words);
      if(ans >= INF) return 0;
      answer = ans;
      return answer;
  }

---

3. 전체코드

#include <string>
#include <vector>

using namespace std;
const int INF = 987654321;

int ans = INF;

void dfs(string now, string target, int depth, vector<bool>& visited, vector<string>& words) {
    if(ans < depth) return;
    if(now == target) {
        ans = min(ans,depth);
        return;
    }

    for(int i = 0; i < words.size(); i++) {
        if(visited[i]) continue;
        int cnt = 0;
        for(int j = 0; j < words[i].size(); j++) {
            if(now[j] != words[i][j]) cnt++;
        }
        if(cnt == 1) {
            visited[i] = true;
            dfs(words[i],target,depth+1,visited,words);
            visited[i] = false;
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    bool found = false;
    for(int i = 0; i < words.size(); i++) {
        if(words[i] == target) found = true;
    }
    if(!found) return 0;
    vector<bool> visited(words.size(),false);
    dfs(begin,target,0,visited,words);
    if(ans >= INF) return 0;
    answer = ans;
    return answer;
}