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

문제 링크 

 

 

맞았습니다 코드 

 

#include <string>
#include <vector>
#include <queue>
using namespace std;

bool check[51]; // 확인 여부 

int solution(string begin, string target, vector<string> words) {
  int min_cnt = 1e9; // 최소 이동 횟수 
  int vector_size = words.size();
  int word_size = begin.size();

  queue<pair<int,string>> qu;
  qu.push({0, begin});

  while(!qu.empty()){
    int cnt = qu.front().first;
    string current_s = qu.front().second; // 비교 문자열
    qu.pop();

    for(int i = 0; i < vector_size; i++){
      // 이미 확인한 문자 지나감
      if(check[i]) continue;

      // 현재 문자열과 i번째 문자열이 1개만 다른지 확인
      int diff_cnt = 0;
      for(int d = 0; d < word_size; d++){
        if(words[i][d] != current_s[d]) diff_cnt++;
      }

      if(diff_cnt == 1){
        if(words[i] == target) { min_cnt = cnt + 1; break; } // 찾음
    
        qu.push({cnt+1, words[i]}); // 1개만 다르니까 여기로 이동 
        check[i] = true; // 이동했으니까 표시 
      }
    }
  }
  if(min_cnt == 1e9) min_cnt = 0;
  return min_cnt;
}