Funcia
Lv.2bfsgraphhashstring

한 글자씩 바꾸는 단어 사다리

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

말놀이 동아리에서 "단어 사다리" 게임을 합니다. 시작 단어 begin에서 출발해 한 번에 한 글자만 바꿔 가며 목표 단어 target을 만들어야 합니다. 단, 중간에 거치는 단어와 target은 모두 사전 words에 들어 있는 단어여야 합니다.

begin부터 target까지 **거쳐 가는 단어 수(양 끝 포함)**의 최솟값을 반환하세요. 만들 수 없다면 0을 반환합니다.

  • 모든 단어는 길이가 같고 영어 소문자로만 이루어져 있습니다.
  • begin은 words에 들어 있지 않아도 됩니다.

입출력 예

begintargetwordsresult
"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

제한 사항

  • 1≤L=1 \le L = begin.length ≤10\le 10, target과 words의 모든 단어도 길이가 LL입니다.
  • 1≤N=1 \le N = words.length ≤30,000\le 30{,}000, words의 단어는 서로 다릅니다.
  • begin과 target은 서로 다릅니다.
  • 모든 문자열은 영어 소문자로만 이루어져 있습니다.

기대 복잡도

시간
O(N * L)
공간
O(N * L)

입출력 예

begintargetwords기대 출력
"hit""cog"["hot","dot","dog","lot","log","cog"]5
"hit""cog"["hot","dot","dog","lot","log"]0
"abc""abd"["abd"]2

힌트

힌트

단어를 정점, "한 글자만 다른 두 단어"를 간선으로 보면 BFS 최단 거리 문제입니다.

어려운 부분은 이웃을 찾는 방법입니다. 큐에서 단어를 꺼낼 때마다 사전 전체와 비교하면 O(N2L)O(N^2 L)이 되어 시간 초과가 납니다.

  • 와일드카드 묶음: 각 단어에서 한 글자를 *로 바꾼 패턴(h*t, *it, ...)을 키로 하는 해시 맵에 단어를 모아 두면, 같은 패턴에 속한 단어끼리가 곧 이웃입니다. 한 번 펼친 패턴은 다시 볼 필요가 없도록 지워 두세요.
  • 또는 각 자리를 a~z로 바꿔 본 단어가 사전(해시 집합)에 있는지 확인해도 됩니다.

어느 쪽이든 전체 O(N⋅L)O(N \cdot L) (해시 비용 제외) 정도로 끝납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)518 ms추정
C++ (GCC, gnu++23)518 ms도출됨
Python 3.131000 ms도출됨
Java 251620 ms도출됨
Kotlin 2.4 (JVM)2036 ms추정
C# 14 (.NET 10)2036 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4011판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.