728x90
programmers.co.kr/learn/courses/30/lessons/43163
코딩테스트 연습 - 단어 변환
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수
programmers.co.kr
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
int solution(string begin, string target, vector<string> words) {
int answer = 0;
queue<int>q;
vector<int>check(words.size(),-1);
bool toggle= false;
for(int i=0; i<words.size(); i++){
if(words[i]==target){toggle =true; break;}
}
if(toggle==false){return 0;}
q.push(-1);
int idx;
while(!q.empty()){
idx = q.front();
q.pop();
string str;
if(idx == -1){str =begin;}
else{
str =words[idx];
}
for(int i=0; i<words.size(); i++){
int count =0;
// if(check[i]==-1){
for(int j=0; j<str.size(); j++){
if(words[i][j]==str[j]){ //같은 문자가 같은 위치에 있는지 체크해야함, 그냥 words[i].find(str[j])는 안됨!
count++;
}
}
if(count==str.size()-1){
if(idx==-1){check[i]=1;}
else{
check[i]=check[idx]+1;
}
if(words[i]==target){return check[i];}
q.push(i);
}
// }
}
}
return 0;
}