✅ LV. 3
🔖 BFS
words
에서 현재 단어와 한 문자 차이 나는 단어 찾기bool check
함수: 현재 단어와 비교 단어가 한 문자 차이나면 true
visit
비교해서 현재 단계가 더 낮을 떄만 큐(비교 단어 후보) 에 비교 단어pushvisit
에 거리 기록 ➡️ words
의 단어를 모두 unodered_map
에 저장하고 visit
값은 0으로 초기화unordered_map<string,int> visit
: string
에 단어, int
에 visit
값 등록words
의 단어들이 중복되지 않기 때문에 map
으로 구현 가능!begin
이 아닐 때만 현재 단계를 현재 단어의 visit
값으로 등록int v
함수: 단어가 저장되어 있는 visit
값을 조회를 빈번하게 하기 때문에 visit
값 조회하는 함수를 따로 구현push
visit
값을 step(현재 단계)+1
로 변경visit
값이 0이 아니면서 현재 단계보다 작거나 같을 경우, 이미 최단거리 방법을 찾은 것이기 때문에 그 루트로 탐색하지 않기 위해 continue
target
의 visit
값을 answer
로 지정. target
이 words
에 없을 경우 0map
의 key
에 대한 값을 조회할 때 코드auto it = map.find(key);
if(it!=map.end()) cout << it->first << it->second;
find
결과가 존재하는지 확인해야 함it->first
: key
값it->second
: value
값#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <iostream>
using namespace std;
queue<string> q;
unordered_map<string,int> visit;
bool check(string begin, string str) {
int cnt=0;
for(int i=0;i<begin.size();i++) {
if(begin[i]!=str[i]) cnt++;
}
if(cnt==1) return true;
return false;
}
int v(string str) {
auto it= visit.find(str);
if(it!=visit.end()) return it->second;
else return -1;
}
int bfs(string begin,int step,vector<string> words,string target) {
q.push(begin);
int k;
while(!q.empty()) {
begin=q.front();
q.pop();
if(v(begin)!=-1) step=v(begin);
for(int i=0;i<words.size();i++) {
string str=words[i];
k=v(str);
if(k!=0 && k<=step) continue;
//한 글자 차이 날 경우
if(check(begin,str)) {
q.push(str);
visit[str]=step+1;
}
}
}
int res=v(target);
if(res==-1) return 0;
else return res;
}
int solution(string begin, string target, vector<string> words) {
int answer = 0;
for(int i=0;i<words.size();i++) {
visit.insert({words[i],0});
}
answer=bfs(begin,0,words,target);
return answer;
}