단어 변환
Prov
두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, begin을 target으로 변환할 수 있는 최소 단계의 과정
Solv
DFS
now의 한 글자씩 제외하고 words와 비교하며 같을 경우 반복
begin부터 now에 넣고 시작
visit으로 선택했던 단어는 제외
now와 target이 같을 경우 convert 반환
같은 경우가 없으면 0 반환
convert 중 최솟값 선별
없으면 target으로 변환 못한 것이니 0
Check
begin = “hit”
words = [“hot”, “dot”, “dog”, “lot”, “log”, “cog”]
convert 0 : hit
| now | words |
|---|---|
| it | ot |
| ot | |
| og | |
| ot | |
| og | |
| og | |
| ht | ht |
| dt | |
| dg | |
| lt | |
| lg | |
| cg | |
| hi | ho |
| do | |
| do | |
| lo | |
| lo | |
| co |
convert 1 : hot
| now | words |
|---|---|
| ot | ot |
| og | |
| ot | |
| og | |
| og | |
| ht | dt |
| dg | |
| lt | |
| lg | |
| cg | |
| ho | do |
| do | |
| lo | |
| lo | |
| co |
convert 2 : dot
convert 3 : lot
convert 4 : log
convert 5 : dog
convert 6 : cog
convert 5 : cog
convert 3 : dog
convert 4 : log
convert 5 : cog
convert 4 : cog
convert 5 : lot
convert 2 : lot
convert 3 : dot
convert 4 : dog
convert 5 : log
convert 6 : cog
convert 5 : cog
convert 3 : log
convert 4 : dog
convert 5 : cog
convert 4 : cog
convert 5 : dot
