프로그래머스 : 단어 변환

https://programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환

target이 words안에 없으면 바로 0을 리턴합니다.

그리고 begin이 words안에 없으면 words에 넣어줍니다. (BFS시, 편리함을 위해서)

 

이 후, words안에서 서로 한 글자만 차이나는 아이들은 서로 변환이 가능하기 때문에, graph에 넣어서 이어줍니다.

이 후, BFS 실행

from collections import deque
def solution(begin, target, words):
    answer = 0
    if target not in words:
        return 0
    
    if begin not in words:
        words.append(begin)
    
    graph=[[] for _ in range(len(words))]
    visitied = [0] * len(words)
    for i in range(len(words)):
        for j in range(len(words)):
            if j == i :
                continue
            count = 0
            for c in range(len(words[i])):
                if words[i][c] != words[j][c]:
                    count+=1
                    
            if count == 1:
                graph[i].append(j)
                
    begin = words.index(begin)
    target = words.index(target)
    
    queue = deque([begin])
    visitied[begin] = 1
    
    while queue:
        now = queue.popleft()
        
        for i in graph[now]:
            if visitied[i] == 0:
                visitied[i] = visitied[now] + 1
                queue.append(i)
                
    return visitied[target] -1