from collections import deque
def solution(begin, target, words):
if target not in words:
return 0
return BFS(begin, target, words)
def BFS(begin, target, words):
queue = deque()
queue.append((begin, 0))
while queue:
now, step = queue.popleft()
if now == target:
return step
for word in words:
cnt = 0
for i in range(len(now)):
if now[i] != word[i]:
cnt += 1
if cnt == 1:
queue.append((word, step+1))
target 단어가 words에 없을 경우 0을 리턴한다.
target 단어가 words에 있을 경우 BFS를 활용하여 문제를 해결할 수 있다.
begin이 target까지 도달하는 최단거리를 구하는 문제이다.