'''
node: 단어
edge: 한 글자만 다름
weight = 1

BFS로 최단거리 찾기
'''

from collections import deque 
    

def is_adjacent(node, adj):
    return sum(a != b for a,b in zip(node, adj)) == 1

def solution(begin, target, words):
    words.append(begin)
    graph = {word: [] for word in words}
    for i in range(len(words)):
        for j in range(i+1):
            if is_adjacent(words[i], words[j]):
                graph[words[i]].append(words[j])
                graph[words[j]].append(words[i])
                
    visited = {}
    queue = deque([(begin, 0)])
    answer = 0
    
    while queue:
        node, d = queue.popleft()
        if node == target:
            answer = d
            break
        if node in visited:
            continue
        
        visited[node] = d
        for adj in graph[node]:
            queue.append((adj, d+1))
            
    return answer

'''
dijkstra와 비슷한 풀이
'''
def solution(begin, target, words):
    words.append(begin)
    graph = {word: [] for word in words}
    for i in range(len(words)):
        for j in range(i+1):
            if is_adjacent(words[i], words[j]):
                graph[words[i]].append(words[j])
                graph[words[j]].append(words[i])
                
    distance = {word: float('inf') for word in words}
    queue = deque([(begin, 0)])
    
    while queue:
        node, d = queue.popleft()
        if distance[node] < d:
            continue
        
        for adj in graph[node]:
            if distance[adj] > d+1:
                distance[adj] = d+1
                queue.append((adj, d+1))
            
    target_d = distance.get(target, 0)
    return target_d if target_d != float('inf') else 0

"""
<양방향 그래프>
node: 각 단어
edge: 단어가 알파벳 하나 차이인 경우 연결

node의 key는 시작노드(begin)으로부터 거리
edge의 가중치가 1이고 양방향이므로 BFS 풀이 가능

begin과 target이 연결되어 있지 않으면, 즉 target의 거리가 무한대이면 0 반환
"""
from collections import deque

def is_adjacent(first, second):
    # diff_num = sum(first[i] != second[i] for i in range(len(first)))
    diff_num = 0
    # zip()보다 이게 시간복잡도에서 우위?
    for i in range(len(first)):
        if first[i] != second[i]:
            diff_num += 1
        if diff_num > 2:
            break
    
    return diff_num == 1

def bfs(graph, begin):
    queue = deque([begin])
    invisited = set(graph)  # 큐에 담긴 적 없는 노드들
    
    while queue:
        node = queue.popleft()
        # 연산 횟수 줄이기 위해 words 대신 invisited에서만 인접노드 추출
        adj_nodes = set(adj for adj in invisited if is_adjacent(node, adj))

        """
        [별해] 인접노드 구하기와 인접노드에 대한 relax 반복문을 합쳐서
        모든 노드에 대해 인접하고 큐에 넣은 적 없을 때 relax & enqueue 해도 됨
        """
        for adj in adj_nodes:
            """ [추가] target 도착 시 순회 종료하면 더 빠름 """
            graph[adj] = graph[node] + 1
            queue.append(adj)
        
        invisited -= adj_nodes
    
    return invisited

def solution(begin, target, words):
    """ [개념] BFS에서는 dijkstra와 달리 거리를 초기화할 필요 없다. relax 할 때마다 담아도 됨. """
    
    # begin이 words에 포함되는 경우 고려하여 순서 바꿈
    graph = {word: float('inf') for word in words}  # key=단어: value=거리
    graph[begin] = 0
    
    if target not in graph:
        return 0
    
    invisited = bfs(graph, begin)
    answer = graph[target] if target not in invisited else 0
    
    return answer