문제 설명
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
- 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
- words에 있는 단어로만 변환할 수 있습니다.
예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.
두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.
제한사항
각 단어는 알파벳 소문자로만 이루어져 있습니다.
각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
begin과 target은 같지 않습니다.
변환할 수 없는 경우에는 0를 return 합니다.
입출력 예
begin / target / words / return
"hit" / "cog" / ["hot", "dot", "dog", "lot", "log", "cog"] / 4
"hit" / "cog" / ["hot", "dot", "dog", "lot", "log"] / 0
입출력 예 설명
예제 #1
문제에 나온 예와 같습니다.
예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.
BFS문제이다.
처음엔 단어를 계속 비교해야하나? 했는데 알고보니 이전 단어는 쓸 일이 없던것이다!
이전 단어는 방문처리를 하고 현재단어와 비교하기 때문에 BFS이다.
BFS의 기본 원리는
- queue를 이용함
- queue에서 뺀 노드는 항상 방문처리
- 조건에 맞으면 queue에 push
- 정답일 때 return
이건데 이에 맞게 코드를 짜면된다.
코드는 다음과 같다.
function solution(begin, target, words) {
let answer = 0;
let visited = [];
let queue = [];
if(!words.includes(target)) return 0; //words배열에 target이 없으면 0을 반환
queue.push([begin,answer]); //일단 queue에 [시작단어, 변경횟수]를 배열형태로 넣는다.
while(queue) {
let [v, cnt] = queue.shift(); //queue의 맨 왼쪽 값을 꺼낸다.
if (v === target) { //꺼낸값의 v가 맞으면 cnt는 횟수 이므로 cnt를 return한다.
return cnt;
}
words.forEach(word => {
let notEqual = 0; //다른갯수를 구하기위해 변수를 선언한다.
if(visited.includes(word)) return; //방문했던 단어면 pass
for (let i=0; i<word.length; i++) {
if (word[i] !== v[i]) notEqual++; //word를 반복하면서 다른 알파벳의 갯수를 체크한다
}
if (notEqual === 1) { //만약 다른게 1개라면
queue.push([word, ++cnt]); //queue에 [단어, 횟수] 형태로 넣는다.
//처음으로 따지면 hit -> hot이 되었을 때가 1이 된다.
visited.push(word); //방문처리를 해준다.
}
});
}
return answer;
}처음 코드를 완성했을때 변경횟수에 대한걸 어떻게 해야하나 고민했다.
cnt를 변수로 선언하고 words.forEach() 다음에 cnt++형태로 했는데 큐에서 하나를 꺼낼때마다 +1 되었다.
검색을 통해 알게된것이 let [v, cnt] = queue.shift(); 형태이다.
같은 단어에서 파생된 단어의 경우 (hot -> lot/dot 의 경우) 같은 변경횟수를 가져야하기 때문에 애초에 queue에 변경횟수를 같이 넣어주면 되는 것이었다.
