[프로그래머스] DFS/BFS > 단어변환 /JS / 접근법, 문제풀이

문제 설명

두 개의 단어 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개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

 

 

문제 해결 전략

1. BFS 활용: BFS는 큐(Queue)를 사용하여 각 단계를 확장하면서 탐색합니다. 처음에 시작 단어를 큐에 넣고, 큐에서 하나씩 꺼내서 목표 단어에 도달할 때까지 단어 변환을 시도합니다.
2. 단어 변환 조건: 변환이 가능한 단어는 한 글자만 다른 단어입니다. 이를 확인하기 위해 diffWord라는 함수를 사용하여 두 단어가 얼마나 다른지 체크합니다.
3. 방문 체크: 이미 방문한 단어는 다시 방문하지 않도록 visited 배열을 사용합니다. 이는 중복 탐색을 방지하고 효율성을 높이는 데 도움을 줍니다.
4. 목표 단어 도달 시 즉시 종료: 목표 단어에 도달하면 그때까지의 변환 횟수를 반환하고 종료합니다. 만약 BFS 탐색이 끝났는데도 목표 단어에 도달하지 못하면 0을 반환합니다.

---

풀이 코드

      
      
      
    
function solution(begin, target, words) {
    // target이 words 배열에 없으면 변환할 수 없으므로 0을 반환
    if (!words.includes(target)) return 0;  

    const visited = Array.from({ length: words.length }, () => false);  // 방문 여부 배열
    const queue = [[begin, 0]];  // 시작 단어와 변환 횟수(0)를 큐에 삽입

    // 두 단어가 하나만 다른지 체크하는 함수
    function diffWord(word1, word2) {
        let count = 0;
        for (let i = 0; i < word1.length; i++) {
            if (word1[i] !== word2[i]) count++;
        }
        return count === 1;  // 두 단어가 1글자만 다를 경우에만 true 반환
    }

    // BFS 탐색
    while (queue.length) {
        const [currentWord, steps] = queue.shift();  // 큐에서 단어와 변환 횟수를 꺼냄

        // 목표 단어에 도달하면 변환 횟수 반환
        if (currentWord === target) return steps;

        // 아직 변환되지 않은 단어들 탐색
        for (let i = 0; i < words.length; i++) {
            if (!visited[i] && diffWord(currentWord, words[i])) {
                visited[i] = true;  // 방문 처리
                queue.push([words[i], steps + 1]);  // 변환된 단어와 변환 횟수 큐에 삽입
            }
        }
    }

    return 0;  // target에 도달할 수 없으면 0 반환
}

---

풀이 설명

1. 초기 입력 체크:
   • target이 words에 없다면 변환할 수 없으므로 바로 0을 반환합니다.
2. 큐와 BFS 사용:
   • 큐에 [begin, 0]을 넣어 시작 단어와 변환 횟수(0)를 초기값으로 설정합니다. 큐는 탐색할 단어를 관리하며, 각 단어가 몇 번의 변환을 거쳐서 변환될 수 있는지 추적합니다.
3. 단어 비교:
   • diffWord 함수는 두 단어가 정확히 한 글자만 다른지를 판단하여 변환 가능한지 확인합니다. 한 글자만 다르면 그 단어를 큐에 넣습니다.
4. 목표 단어 도달:
   • 목표 단어에 도달하면 바로 그 변환 횟수를 반환합니다. BFS의 특성상 첫 번째로 목표에 도달한 경로가 최단 경로입니다.
5. 종료 조건:
   • BFS 탐색을 다 했음에도 target에 도달하지 못하면 0을 반환합니다.

---

시간 복잡도

• BFS는 큐에 들어가는 단어의 개수만큼 탐색을 하므로, 시간 복잡도는 O(N * M)입니다. 여기서 N은 단어의 개수, M은 각 단어의 길이입니다.
• 각 단어에 대해 다른 모든 단어들과 한 번씩 비교하므로, 전체 시간 복잡도는 O(N^2 * M)입니다. 이 정도 복잡도는 일반적인 코딩 테스트에서 충분히 효율적입니다.

---

개선 사항

• BFS vs DFS: 이 문제는 최단 경로를 구하는 문제이므로, DFS보다는 BFS를 사용하는 것이 효율적입니다. DFS는 모든 경로를 탐색하지만, BFS는 최단 경로를 찾는 데 특화되어 있습니다.
• 방문 배열: 이미 방문한 단어는 다시 방문하지 않도록 처리하여 불필요한 탐색을 줄입니다.