← 16주차 · BFS 최단 거리와 격자 탐색
보통BFS그래프

단어 변환

시작 단어 begin, 목표 단어 target, 사용할 수 있는 단어 목록 words가 주어져요. 모든 단어는 길이가 같아요.

한 번에 한 글자만 바꿀 수 있고, 바꾼 단어는 반드시 words 안에 있어야 해요. begin을 target으로 바꾸는 데 필요한 최소 변환 횟수를 반환해요. 바꿀 수 없으면 0을 반환해요.

여기서 단어 하나하나가 정점이고, '한 글자 차이'가 간선이에요. 지도가 그려져 있지 않을 뿐 BFS로 최단 거리를 구하는 문제와 똑같아요.

예시

예시 1
입력
begin = "hit", target = "cog", words = ["hot", "dot", "dog", "lot", "log", "cog"]
출력
4
설명
hit → hot → dot → dog → cog, 네 번 바꿔요.
예시 2
입력
begin = "hit", target = "cog", words = ["hot", "dot", "dog", "lot", "log"]
출력
0
설명
목표 cog가 목록에 없어 도달할 수 없어요.

제한 사항

  • 1 ≤ 단어 길이 ≤ 10, 모든 단어의 길이가 같아요.
  • 1 ≤ words.length ≤ 5,000
  • 단어는 소문자 알파벳으로만 이루어져요.
words를 집합에 넣어 두고, begin에서 BFS를 시작해요. 각 단어의 모든 자리를 a~z로 하나씩 바꿔 보고, 그 단어가 집합에 있고 아직 방문하지 않았으면 변환 횟수를 1 늘려 큐에 넣어요. target에 닿으면 그 횟수가 답이에요.
javascript
function wordLadder(begin, target, words) {
  const set = new Set(words);
  if (!set.has(target)) return 0;
  const dist = new Map([[begin, 0]]);
  const queue = [begin];
  let head = 0;
  while (head < queue.length) {
    const word = queue[head++];
    if (word === target) return dist.get(word);
    for (let i = 0; i < word.length; i++) {
      for (let c = 97; c < 123; c++) {
        const next = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
        if (set.has(next) && !dist.has(next)) {
          dist.set(next, dist.get(word) + 1);
          queue.push(next);
        }
      }
    }
  }
  return 0;
}
이전 문제토마토 익히기
다음 문제벽 부수고 이동하기
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.