6125 : 단어 사다리
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
한 글자씩 다른 단어로 변환하며 타겟 단어로 이동하는 단어 사다리 게임의 최소 단계를 구하십시오. (6097번 문제의 대규모 스케일 버전입니다.)
N이 커질 수 있으므로 반드시 너비 우선 탐색(BFS) 기법을 사용해 문제를 해결해야 합니다.
N이 커질 수 있으므로 반드시 너비 우선 탐색(BFS) 기법을 사용해 문제를 해결해야 합니다.
입력 설명
첫째 줄에 시작 단어(start)와 대상 단어(end)가 공백 구분되어 주어집니다.
둘째 줄에 단어 목록 단어 수 N (1 ≤ N ≤ 500)이 주어집니다.
셋째 줄부터 N개의 줄에 단어들이 주어집니다.
둘째 줄에 단어 목록 단어 수 N (1 ≤ N ≤ 500)이 주어집니다.
셋째 줄부터 N개의 줄에 단어들이 주어집니다.
출력 설명
시작 단어에서 끝 단어로 변환할 수 있는 최소 단계 수를 출력합니다. 변환할 수 없으면 0을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
hit cog
6
hot
dot
dog
lot
log
cog
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4도움
단어들 중 글자 수가 한 글자만 차이 나는 관계를 그래프의 무방향 무가중치 간선으로 정의한 후, BFS 최단 거리를 탐색하여 답을 내십시오.