[프로그래머스] (JavaScript) 단어 변환 - BFS

[프로그래머스] (JavaScript) 단어 변환 - BFS

문제 설명

두 개의 단어 begin, target 과 단어의 집합 words 가 있다. 아래의 규칙을 이용하여 begin 에서 target 으로 변환하는 가장 짧은 변환 과정을 찾으려 한다.

 

1. 한 번에 한 개의 알파벳만 바꿀 수 있다.
2. 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개 이하의 단어가 있으며, 중복 X
• 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 안에 없기 때문에 변환할 수 없음

---

정답 코드

function solution(begin, target, words) {
    let answer = 0;
    const visited = new Array(words.length).fill(false);
    const queue = [[begin, answer]];
    
    while (queue.length) {
        let [word, answer] = queue.shift();
        if (word == target) return answer;

        for (let i = 0; i < words.length; i++) {
            let diffCnt = 0;
            if (visited[i]) continue;
            
            for (let j = 0; j < word.length; j++) {
                if (word[j] == words[i][j]) {
                    continue;
                } else {
                    diffCnt++;
                }
                if (diffCnt > 1) break;
            }
            if (diffCnt == 1) {
                visited[i] = true;
                queue.push([words[i], answer + 1])
            }
        }
    }
    return answer;
}

---

코드 풀이

const visited = new Array(words.length).fill(false);
const queue = [[begin, answer]];

 

각 words 의 방문 여부를 담는 배열 visited 와, 단어를 변환할 때의 단어와 변환 횟수를 담는 queue 를 생성해 준다.

 

 while (queue.length) {
        let [word, answer] = queue.shift();
        if (word == target) return answer;

//      for (let i = 0; i < words.length; i++) {
//          let diffCnt = 0;
//          if (visited[i]) continue;
            
//          for (let j = 0; j < word.length; j++) {
//              if (word[j] == words[i][j]) {
//                  continue;
//              } else {
//                  diffCnt++;
//              }
//              if (diffCnt > 1) break;
//          }
//          if (diffCnt == 1) {
//              visited[i] = true;
//              queue.push([words[i], answer + 1])
//         }
//      }
//  }
//  return answer;
}

 

queue 의 길이가 0이 아닐때까지 while 문이 반복하는데, 반복할 때마다 queue 의 맨 앞에 있는 수를 shift( ) 하여 현재 단어인 word 와 현재 변환 횟수인 answer 을 변수에 담아준다.

 

그리고 그 word 와 target 이 같으면 변환 횟수인 answer 을 return 해준다.

 

for (let i = 0; i < words.length; i++) {
    let diffCnt = 0;
    if (visited[i]) continue;
            
//  for (let j = 0; j < word.length; j++) {
//      if (word[j] == words[i][j]) {
//          continue;
//      } else {
//          diffCnt++;
//      }
//      if (diffCnt > 1) break;
//  }
//  if (diffCnt == 1) {
//      visited[i] = true;
//      queue.push([words[i], answer + 1])
//  }
}

 

그리고 해당 word 를 words[i] 단어를 전부 비교한다.

 

한 알파벳만 달라야 하니, 다른 횟수를 담는 diffCnt 변수를 생성하고, words[i] 단어로 이미 바뀌었던 단어이면 비교하는 for 문을 돌지 않고 다음 words[i] 과 비교하기 위해 continue 한다.

 

for (let j = 0; j < word.length; j++) {
    if (word[j] == words[i][j]) {
        continue;
    } else {
        diffCnt++;
    }
    if (diffCnt > 1) break;
}
// if (diffCnt == 1) {
//     visited[i] = true;
//     queue.push([words[i], answer + 1])
// }

 

방문 여부가 false 인 words[i] 와 현재 단어 word 가 j 번째의 알파벳이 서로 같으면 j + 1 번째 알파벳을 비교하기 위해 continue 하고, 다르면 diffCnt 를 올린다.

 

그렇게 알파벳 하나씩 비교하다가 다른 횟수인 diffCnt 가 1 보다 크면 2개 이상 알파벳이 다른 단어이므로 다음 words[i] 와 비교하기 위해 해당 for 문을 종료한다.

 

if (diffCnt == 1) {
    visited[i] = true;
    queue.push([words[i], answer + 1])
}

 

위의 for 문을 정상적으로 다 돌고 난 뒤 diffCnt 가 1인 words[i] 를 찾아 해당 words[i] 를 방문 처리한 후, 해당 word 를 words[i] 로 바꾸고 answer + 1 을 한 뒤 queue 에 넣어준다.

---

풀이 상세

하나씩 순차적으로 실행하여 가장 빨리 찾아진 것이 최단 방법이므로 순열을 이용한 BFS 방식으로 풀었다.

 

입출력 예시로 설명해 보겠다.

 

begin : "hit"

target : "cog"

words : ["hot", "dot", "dog", "lot", "log", "cog"]

 

queue ["hit", 0], (f, f, f, f, f, f)

queue.shift( ) → queue [ ]

"hit", 0

    i = 0 → "hit" hot && f [조건 O] → queue ["hot", 1], (t, f, f, f, f, f)

    i = 1 → "hit" dot [조건 X]

    i = 2 → "hit" dog [조건 X]

    i = 3 → "hit" lot [조건 X]

    i = 4 → "hit" log [조건 X]

    i = 5 → "hit" cog [조건 X]

queue ["hot", 1], (t, f, f, f, f, f)

queue.shift( ) → queue [ ]

"hot", 1

    i = 0 → t [조건 X]

    i = 1 → "hot" dot && f [조건 O] → queue ["dot", 2], (t, t, f, f, f, f)

    i = 2 → "hot" dog [조건 X]

    i = 3 → "hot" lot && f [조건 O] → queue ["dot", 2] ["lot", 2], (t, t, f, t, f, f)

    i = 4 → "hot" log [조건 X]

    i = 5 → "hot" cog [조건 X]

queue ["dot", 2] ["lot", 2], (t, t, f, t, f, f)

queue.shift( ) → queue ["lot", 2]

"dot", 2

    i = 0 → t [조건 X]

    i = 1 → t [조건 X] 

    i = 2 → "dot" dog && f [조건 O] → queue ["lot", 2] ["dog", 3], (t, t, t, t, f, f)

    i = 3 → t [조건 X]

    i = 4 → "dot" log [조건 X]

    i = 5 → "dot" cog [조건 X]

queue ["lot", 2] ["dog", 3], (t, t, t, t, f, f)

queue.shift( ) → queue ["dog", 3]

"lot", 2

    i = 0 → t [조건 X]

    i = 1 → t [조건 X]    

    i = 2 → t [조건 X]

    i = 3 → t [조건 X]

    i = 4 → "lot" log && f [조건 O] → queue ["dog", 3] ["log", 3], (t, t, t, t, t, f)

    i = 5 → "lot" cog [조건 X]

queue ["dog", 3] ["log", 3], (t, t, t, t, t, f)

queue.shift( ) → queue ["log", 3]

"dog", 3

    i = 0 → t [조건 X]

    i = 1 → t [조건 X]  

    i = 2 → t [조건 X]

    i = 3 → t [조건 X]

    i = 4 → t [조건 X]

    i = 5 → "dog" cog && f [조건 O] → queue ["log", 3] ["cog", 4], (t, t, t, t, t, t)

queue ["log", 3] ["cog", 4], (t, t, t, t, t, t)

queue.shift( ) → queue ["cog", 4]

"log", 3

    i = 0 → t [조건 X]

    i = 1 → t [조건 X]

    i = 2 → t [조건 X]

    i = 3 → t [조건 X]

    i = 4 → t [조건 X]

    i = 5 → t [조건 X]

queue ["cog", 4], (t, t, t, t, t, t)

queue.shift( ) → queue [ ]

"cog", 4

    "cog" == target > answer 4