<Programmers> DFS/BFS_단어 변환 (convert words) c++

단어 변환 문제 링크

문제에 나와있는 예시
[hot, dot, dog, lot, log, cog]에서 hit->cog 로 가는 방법을 도식화하면 이렇게 나타낼 수 있다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있기 때문에 현재 단어와 한 글자만 다른 단어를 찾는 함수를 만든다

bool wordCheck(string a, string b) {
    int cnt=0; 
    for (int i=0; i<a.size(); i++) {
        if (a[i]!=b[i])
            cnt++;
    }
    if (cnt==1) return true;    
    return false;
}

2. 단어가 변경될 때마다 1단계씩마다 늘어나는 것을 표현해주기 위해 DFS함수의 파라메터를 void dfs(string begin, string target, vector<string>words, int step) 로 한다.

3. DFS함수의 종료조건은 현재까지의 step이 이전에 단어를 찾았을 때 최소 단계 (answer)보다 크거나 같을 때, 그리고 현재 단어가 target과 같을 때

     if (answer<=step)
         return; 
     if (begin==target) {
         answer=min(answer, step);
         return;
     }

소스코드

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

using namespace std;
int answer = 50;
vector<bool> visited;

bool wordCheck(string a, string b) {
  int cnt=0;
 
  for (int i=0; i<a.size(); i++) {
      if (a[i]!=b[i])
          cnt++;
  }
  if (cnt==1) return true;
 
  return false;
}

void dfs(string begin, string target, vector<string>words, int step) {
  if (answer<=step)
      return;
 
  if (begin==target) {
      answer=min(answer, step);
      return;
  }

  for (int i=0; i<words.size(); i++) {
      if (wordCheck(begin, words[i]) && !visited[i]) {
          visited[i]=true;
          dfs(words[i], target, words, step+1);
          visited[i]=false;
      }
  }
  return;
}

int solution(string begin, string target, vector<string> words) {
  visited=vector<bool>(words.size(), false);
 
  dfs(begin, target, words, 0);
 
  if (answer==50) return 0;

  return answer;
}