words 리스트 내의 각 단어까지 가는 데 걸린 거리(단계)를 누적해서 저장할 words_dist 리스트를 추가로 생성하여 BFS로 구현
from collections import deque
def bfs(begin, target, words):
words_dist = [0] * len(words) # 해당 인덱스에 위치한 단어까지 가는데 걸린 단계를 저장할 리스트
q = deque()
q.append((begin, 0))
is_finish = False
target_idx = -1
while q:
word, idx = q.popleft()
# word와 알파벳 하나 차이나는 단어와 그 인덱스를 모두 찾기
for i in range(0, len(words)):
if words_dist[i] != 0: # 이미 방문한 단어라면 패스
continue
diff_cnt = 0 # 차이나는 알파벳 개수 누적할 변수
for j in range(0, len(word)): # 현재 단어 word와 words[i]의 알파벳 차이 체크
if word[j] != words[i][j]: # 알파벳이 다름
diff_cnt += 1
if diff_cnt >= 2: # 2개 이상 차이나면 더 볼 필요없음
break
if diff_cnt == 1: # i번째 단어가 방문 가능한 단어라면 (차이 = 1)
if words[i] == target: # target 단어를 찾았다면 반복문 종료
is_finish = True
target_idx = i
words_dist[i] = words_dist[idx] + 1 # 현재 방문한 거리 누적
q.append((words[i], i)) # 다음에 방문하도록 큐에 저장
if is_finish:
break
if is_finish:
break
if target_idx == -1: # target 단어를 찾지 못했다면
return 0
return words_dist[target_idx] # target 단어까지 가는 데 누적된 거리 반환
def solution(begin, target, words):
answer = bfs(begin, target, words)
return answer