[프로그래머스 | BFS/DFS] 단어 변환 - Python

def check_similar(a, b):
    cnt = 0
    for A, B in zip(a, b):
        if A != B:
            cnt += 1
    if cnt == 1:
        return True
    else:
        return False
    
def solution(begin, target, words):
    answer = 0    
    if target not in words:
        return answer
    
    from collections import deque
    # Make Graph
    size = len(words) + 1
    graph = [[0] * size for _ in range(size)]
    words.insert(0, begin)
    for i in range(len(words)-1):
        for j in range(i, len(words)):
            a = words[i]
            b = words[j]
            if check_similar(a, b):
                graph[i][j] = 1
                graph[j][i] = 1
    
    visited = [False] * size
    
    # BFS & Record shortest path directly at graph
    # q에는 단어의 인덱스 관리 (begin-0부터)
    q = deque()
    q.append(0) # set begin as root
    while q:
        rootidx = q.pop()
        for idx, connected in enumerate(graph[rootidx]):
            if connected != 0 and visited[idx] == False:
                q.append(idx)
                graph[idx][idx] = min(graph[idx][idx], graph[rootidx][rootidx]+1) if graph[idx][idx]!=0 else graph[rootidx][rootidx]+1
                visited[idx] = True
    # Get shortest path
    targetidx = words.index(target)
    answer = graph[targetidx][targetidx]
    
    print(graph)
    
    return answer

어렵군!

BFS로 탐색

1. words 배열을 돌며 이동 가능한 단어들 쌍을 찾아 그래프로 표현
2. 이미 방문한 노드인지를 기록해두는 용도로 visited 배열을 만들어 모두 False로 초기화
3. 큐에 begin 인덱스 넣고 BFS 시작
   1) q.pop으로 탐색할 root 노드 빼오기
   2) root 노드와 연결된 노드들에 대해 방문한 이력이 없다면 큐에 넣고, begin부터의 최단거리를 기록
4. BFS가 종료되면, graph[targetidx][targetidx]에 begin부터 target까지의 최단거리가 저장되어 있음