← 전체 회차
a-092-word-ladder2026-08-20hardleetcode #127neetcode150

단어 사다리

#hash-table#string#breadth-first-search#bidirectional-search
↗ leetcode #127 · a-092-word-ladder
01

문제

· problem
P.a-092-word-ladder

단어 사다리

↗ leetcode #127

단어 beginWord에서 단어 endWord로의 변환 수열은 다음 조건을 만족하는 단어들의 수열입니다: 인접한 단어 쌍은 정확히 한 글자만 다릅니다. 모든 중간 단어는 wordList에 있어야 합니다. beginWord는 wordList에 없어도 됩니다. 마지막 단어는 endWord와 같아야 합니다. 두 단어 beginWord와 endWord, 그리고 사전 wordList가 주어질 때, beginWord에서 endWord로의 최단 변환 수열에 포함된 단어의 개수를 반환하세요. 그러한 수열이 없으면 0을 반환하세요.

제약
  • · 1 ≤ beginWord.length ≤ 10
  • · endWord.length == beginWord.length
  • · 1 ≤ wordList.length ≤ 5000
  • · All words consist of lowercase English letters
  • · beginWord ≠ endWord
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
"hit"
"cog"
["hot","dot","dog","lot","log","cog"]
5
example 2input → output
"hit"
"cog"
["hot","dot","dog","lot","log"]
0
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    정확히 한 글자만 다른다는 것은 무엇을 의미하나요?
  • ☐
    최단 경로 자체를 반환해야 하나요, 아니면 경로의 길이만 반환하나요?
  • ☐
    각 단어를 변환 경로에서 두 번 이상 사용할 수 있나요?
  • ☐
    beginWord가 wordList에 포함되어야 하나요?
  • ☐
    최단 경로가 여러 개 있으면 사전순이 가장 작은 것을 반환해야 하나요?
  • ☐
    BFS 대신 DFS를 사용하여 최단 경로를 찾을 수 있나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· endWord 존재 여부 확인
○
if endWord not in wordList:
○
if beginWord not in wordList:
○
if endWord not in wordList or len(wordList) == 0:
step 2· 와일드카드 패턴 생성│ │ 중첩
○
pattern = word[:j] + "*" + word[j + 1 :]
○
pattern = word[:j] + "*" + word[j + 2:]
○
pattern = "*" * len(word)
step 3· 시작 단어 방문 표시
○
visit = set([beginWord])
○
visit = set(wordList)
○
visit = set()
step 4· BFS 메인 루프 시작
○
while q:
○
while len(q) > 0:
○
for _ in range(len(wordList)):
step 5· 도착지 확인 및 반환│ │ 중첩
○
if word == endWord:
○
if neiWord == endWord:
○
if word == endWord: res -= 1; return res
step 6· 거리 카운터 증가│ 중첩
○
res += 1
○
res += len(q)
○
res += 1 (inside inner for loop)
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
3
        if endWord not in wordList:
4
            return 0
5
6
        nei = collections.defaultdict(list)
7
        wordList.append(beginWord)
8
        for word in wordList:
9
            for j in range(len(word)):
10
                pattern = word[:j] + "*" + word[j + 1 :]
11
                nei[pattern].append(word)
12
13
        visit = set([beginWord])
14
        q = deque([beginWord])
15
        res = 1
16
        while q:
17
            for i in range(len(q)):
18
                word = q.popleft()
19
                if word == endWord:
20
                    return res
21
                for j in range(len(word)):
22
                    pattern = word[:j] + "*" + word[j + 1 :]
23
                    for neiWord in nei[pattern]:
24
                        if neiWord not in visit:
25
                            visit.add(neiWord)
26
                            q.append(neiWord)
27
            res += 1
28
        return 0
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
"hit"
"cog"
["hot","dot","dog","lot","log","cog"]
→
5
case 2
"hit"
"cog"
["hot","dot","dog","lot","log"]
→
0
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.