6097 : 단어 변환 DFS — 단어 사다리
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
시작 단어(start)와 대상 단어(end), 그리고 단어들의 목록이 주어집니다. 한 번에 한 글자씩만 바꿀 수 있으며, 변환 과정의 모든 단어는 단어 목록에 있는 단어여야 합니다.
시작 단어에서 대상 단어로 변환할 수 있는 최소 단계 수를 구하는 프로그램을 작성하십시오. 변환이 불가능한 경우 0을 출력합니다.
[제약 조건]
• 단어 길이: $1 \le$ 길이 $\le 10$ (모든 단어 길이 동일)
• 단어 목록 수 $N$: $1 \le N \le 50$ (정수)
• 변환 불가능하면 0을 출력합니다.
시작 단어에서 대상 단어로 변환할 수 있는 최소 단계 수를 구하는 프로그램을 작성하십시오. 변환이 불가능한 경우 0을 출력합니다.
[제약 조건]
• 단어 길이: $1 \le$ 길이 $\le 10$ (모든 단어 길이 동일)
• 단어 목록 수 $N$: $1 \le N \le 50$ (정수)
• 변환 불가능하면 0을 출력합니다.
입력 설명
첫째 줄에 시작 단어(start)와 대상 단어(end)가 공백을 사이에 두고 주어집니다. (단어의 길이는 서로 같으며 10자 이하입니다.)
둘째 줄에 단어 목록에 있는 단어의 개수 N (1 ≤ N ≤ 50)이 주어집니다.
셋째 줄부터 N개의 줄에 걸쳐 단어 목록의 단어들이 한 줄에 하나씩 주어집니다.
둘째 줄에 단어 목록에 있는 단어의 개수 N (1 ≤ N ≤ 50)이 주어집니다.
셋째 줄부터 N개의 줄에 걸쳐 단어 목록의 단어들이 한 줄에 하나씩 주어집니다.
출력 설명
변환 가능한 최소 단계 수를 출력합니다. 불가능한 경우 0을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
hit cog
6
hot
dot
dog
lot
log
cog
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4도움
단어 목록을 그래프의 노드로 모델링하고, 한 글자만 다른 단어들 사이에 간선을 정의합니다. DFS 백트래킹을 사용하여 최소 탐색 깊이를 찾거나 가지치기를 수행할 수 있습니다.