문제 조건

input

• 문자열 begin, target
  • 3 ≤ (begin, target).len ≤ 10
• 문자열 배열 words
  • 3 ≤ words ≤ 50

output

• 최소 경로

문제 해석

• BFS로 완전 탐색
• 단어를 변환하면서 target에 도달하면 탈출
  • 이때, 누적된 경로 개수를 기존 최단 경로와 비교하면서 갱신
• words 배열에 target이 없으면 무조건 실패
  • 0 리턴

코드

1. index를 증가 시킨 버전

   def solution(begin, target, words):
       
       # words 배열에 target이 없는 경우에 대한 처리
       if target not in words:
           return 0
       
       # 문제 조건에 의해 최대 50
       min_len = 50
       
       def bfs(current_word, cnt):
           nonlocal min_len
           
           # 탈출 조건
           if current_word == target:
               min_len = min(cnt, min_len)
               return 
           
           # 탐색 횟수인 cnt를 탐색의 시작점으로 시작
           # 문제 test case에서 이런식으로 접근해서 이렇게 해도 된다고 생각 -> 잘못된 접근
           for i in range(cnt, len(words)):
                   diff_cnt = 0
                   word = words[i]
                   
                   for j in range(len(word)):
   		                # 문자열을 비교하면서 diff가 몇개인지 판단
                       if word[j] != current_word[j]:
                           diff_cnt += 1
                   
                   # diff가 1이면 변환 가능 -> 이동 가능
                   if diff_cnt == 1:
                       bfs(word, cnt+1)
       
       bfs(begin, 0)
       
       return min_len
   

   • 3번 test case 실패
     • "hit", "cog", ["cog", "hot", "dot", "dog", "lot", "log"]
     • 위 반례 찾음
       • 즉, 탐색 횟수인 cnt를 탐색의 시작점으로 시작하면 안 되고
       • 방문을 기록할 set이 필요

2. 방문을 기록한 set 버전

   def solution(begin, target, words):
       
       if target not in words:
           return 0
       
       min_len = 50
       # 방문한 단어를 기록할 set
       visited = set()
       
       def bfs(current_word, cnt):
           nonlocal min_len 
           
           if current_word == target:
               min_len = min(cnt, min_len)
               return 
               
           for word in words:
   		        # 방문한 적이 없다면, 진행
               if word not in visited:
                   diff_cnt = 0
                   
                   for j in range(len(word)):
                       if word[j] != current_word[j]:
                           diff_cnt += 1
                   
                   if diff_cnt == 1:
   		                # 백트래킹
                       visited.add(word)
                       bfs(word, cnt+1)
                       visited.remove(word)
       
       bfs(begin, 0)
       
       return min_len