"""
입출력 예시)
begin = "hit", target = "cog", words = ["hot", "dot", "dog", "lot", "log", "cog"] -> 4
begin = "hit", target = "cog", words = ["hot", "dot", "dog", "lot", "log"] -> 0
"""
from collections import deque
def solution(begin, target, words):
answer = 0
q = deque()
q.append([begin, 0]) # 0: 깊이
visited = [ 0 for i in range(len(words))]
# target 단어가 words 안에 없으면 변환할 수 없음 -> 0을 return
if target not in words:
answer = 0
while q:
word, cnt = q.popleft() # 큐에 삽입된 순서대로 단어(word)와 깊이(cnt)를 뽑음
if word == target:
answer = cnt
break
for i in range(len(words)): # i -> len(words)
temp_cnt = 0
# 아직 방문하지 않은 노드라면
if not visited[i]: # visited[i] = 0일 때 아래 코드 동작
for j in range(len(word)): # j -> len(word)
# word의 j번째 알파벳이 words 리스트의 i번째 단어의 j번째 알파벳과 같지 않은 경우
if word[j] != words[i][j]:
temp_cnt += 1
if temp_cnt == 1:
q.append([words[i], cnt+1])
visited[i] = 1
return answer
begin에서 target으로 변환하는 가장 짧은 변환 과정 찾기 -> BFS 이용
if not False
0, None, 빈 문자열 ''을 not으로 뒤집으면 참이 되므로 if를 동작시킬 수 있음