두 개의 단어 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 함수를 작성해주세요.
function solution(begin, target, words) {
const visited = [];
const queue = [];
if (!words.includes(target)) return 0;
queue.push([begin, 0]);
while (queue.length) {
const [cur, cnt] = queue.shift();
visited.push(cur);
if (cur === target) {
return cnt;
}
for (let next of words) {
if (visited.includes(next)) continue;
let len = 0;
for (let i = 0; i < next.length; i++) {
if (cur[i] != next[i]) len++;
}
if (len === 1) {
queue.push([next, cnt + 1]);
}
}
}
return 0;
}
조건으로 갈 수 있는 단어를 queue에 넣으면 bfs로 최단거리를 찾아냈다.
function solution(begin, target, words) {
const visited = new Array(words.length).fill(false);
if (!words.includes(target)) return 0;
const dfs = (L, str) => {
if (str === target) {
answer = Math.min(answer, L);
} else {
for (let i = 0; i < words.length; i++) {
if (visited[i]) continue;
let cnt = 0;
for (let k = 0; k < words[i].length; k++) {
if (words[i][k] !== str[k]) {
cnt++;
}
}
if (cnt === 1) {
visited[i] = true;
dfs(L + 1, words[i]);
visited[i] = false;
}
}
}
};
let answer = Number.MAX_SAFE_INTEGER;
dfs(0, begin);
return answer;
}
dfs로 해결해봤다.