Lv.2bfsgraphhashstring
한 글자씩 바꾸는 단어 사다리
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
말놀이 동아리에서 "단어 사다리" 게임을 합니다. 시작 단어 begin에서 출발해 한 번에 한 글자만 바꿔 가며 목표 단어 target을 만들어야 합니다.
단, 중간에 거치는 단어와 target은 모두 사전 words에 들어 있는 단어여야 합니다.
begin부터 target까지 **거쳐 가는 단어 수(양 끝 포함)**의 최솟값을 반환하세요. 만들 수 없다면 0을 반환합니다.
- 모든 단어는 길이가 같고 영어 소문자로만 이루어져 있습니다.
begin은words에 들어 있지 않아도 됩니다.
입출력 예
| begin | target | words | result |
|---|---|---|---|
"hit" | "cog" | ["hot", "dot", "dog", "lot", "log", "cog"] | 5 |
"hit" | "cog" | ["hot", "dot", "dog", "lot", "log"] | 0 |
"abc" | "abd" | ["abd"] | 2 |
입출력 예 설명
예 1 — hit → hot → dot → dog → cog로 단어 5개를 거칩니다.
예 2 — 사전에 cog가 없으므로 목표 단어를 만들 수 없습니다.
예 3 — 마지막 글자만 바꾸면 바로 도착하므로 abc, abd 두 단어입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(begin: string, target: string, words: string[]) → int
제한 사항
-
begin.length,target과words의 모든 단어도 길이가 입니다. -
words.length,words의 단어는 서로 다릅니다. begin과target은 서로 다릅니다.- 모든 문자열은 영어 소문자로만 이루어져 있습니다.
기대 복잡도
- 시간
- O(N * L)
- 공간
- O(N * L)
입출력 예
| begin | target | words | 기대 출력 |
|---|---|---|---|
"hit" | "cog" | ["hot","dot","dog","lot","log","cog"] | 5 |
"hit" | "cog" | ["hot","dot","dog","lot","log"] | 0 |
"abc" | "abd" | ["abd"] | 2 |
힌트
힌트
단어를 정점, "한 글자만 다른 두 단어"를 간선으로 보면 BFS 최단 거리 문제입니다.
어려운 부분은 이웃을 찾는 방법입니다. 큐에서 단어를 꺼낼 때마다 사전 전체와 비교하면 이 되어 시간 초과가 납니다.
- 와일드카드 묶음: 각 단어에서 한 글자를
*로 바꾼 패턴(h*t,*it, ...)을 키로 하는 해시 맵에 단어를 모아 두면, 같은 패턴에 속한 단어끼리가 곧 이웃입니다. 한 번 펼친 패턴은 다시 볼 필요가 없도록 지워 두세요. - 또는 각 자리를
a~z로 바꿔 본 단어가 사전(해시 집합)에 있는지 확인해도 됩니다.
어느 쪽이든 전체 (해시 비용 제외) 정도로 끝납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 518 ms | 추정 |
| C++ (GCC, gnu++23) | 518 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1620 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 2036 ms | 추정 |
| C# 14 (.NET 10) | 2036 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 11 | 판정만 |
| performance | 60 | 4 | 판정만 |