function solution(begin, target, words) {
var answer = 0;
if(!words.includes(target)) //예제 #2
// target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다. 예시 조건
return 0;
function oneChar(a,b) { // 한 글자만 차이가 나는지 확인하는 함수
var diff=0;
for(var i=0 ; i<a.length ; ++i) {
if(a[i]!=b[i])
++diff;
}
if(diff==1)
return true;
else return false;
}
var visit=[]; // 방문했는지 기록하는 배열
for(var i = 0 ; i<words.length ; ++i)
visit.push(false);
var q=[];
var temp=[];
q.push(begin);
while(q.length) {
let w=q.shift(); // 방문하였으므로 큐에서 제거
if(w==target)
return answer;
for(var i=0 ; i<words.length ; ++i) {
if(oneChar(w,words[i]) && !visit[i]) { // 한글자 차이면서 방문을 안했다면 방문할 노드(temp)에 추가
temp.push(words[i]); visit[i]=true;
}
}
if(q.length==0) { // 큐가 비었다는 건, 현재 레벨의 모든 단어를 방문한것이므로
++answer; // 방문 수 증가
q=temp; // 큐에 방문할 노드들 추가
temp=[];
}
}
return answer;
}
bfs로 단어들을 방문한다면 트리 구조가 나오게 됩니다.
hit
hot
dot lot
dog log
cog
트리의 레벨이 단어를 바꾼 횟수이므로 바로 큐에 추가하지않고 임시배열에 추가해뒀다가, 레벨이 바뀔때 큐에 추가하였습니다.