[프로그래머스`LV3] 43163 - 단어 변환 (Python)

문제 설명

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

프로그래머스

 

---

문제 풀이

1차원 배열 bfs 문제

target이 없으면 return 0을 해주어 변환할 수 없는 경우에 시간을 줄여주었다

 

한 번에 한 알파벳만 바꿀 수 있다는 규칙이 있어

알파벳이 다른 개수를 구해주는 cnt 함수를 만들어주었고 달라진 알파벳이 1개이면 True를 리턴해주었다

큐를 돌아가면서 cnt 함수 return 값이 True면 현재 visited값과 이전 visited에서 1을 더해준 값 중에 작은 값을 visited에 넣어주었다!

계속 while문을 돌아가면서 만약 큐에서 pop한 단어가 target이면 target에 해당하는 visited 값으로 리턴

 

정리하면서 생각난 건데

제한사항에서 단어의 길이가 길어지거나 배열의 요소 개수가 많아지면

배열의 index 연산은 시간이 걸리기 때문에 검색 속도가 빠른 딕셔너리를 사용해도 좋을 것 같다 !! 

 

from collections import deque

def solution(begin, target, words):
    if target not in words:
        return 0
    
    visited = [9999] * len(words)
    queue = deque()
    queue.append(begin)
    
    while queue:
        w = queue.popleft()
        if w == target:
            return visited[words.index(target)]
        
        for i in range(len(words)):
            if cnt(w, words[i]):       
                queue.append(words[i])
                if w == begin:
                    visited[i] = 1
                else:
                    visited[i] = min(visited[i], visited[words.index(w)] + 1)
            
            
def cnt(a, b):
    count = 0
    for i in range(len(a)):
        if not a[i] == b[i]:
            count += 1
    return True if count == 1 else False