[프로그래머스] 단어 변환 (level3, python)

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

프로그래머스

 

아이디어

bfs를 사용해서 풀었다.

    def bfs(begin, target, words, visited):
        queue = deque([(begin, 0)])
        
        while queue:
            now, c = queue.popleft()
            
            if now == target: 
                return c
            
            for i in range(len(target)):
                if now[i] == target[i]:
                    continue
                    
                try: tmp_now = now[:i] + now[i+1:]
                except: tmp_now = now[:i]
                
                for w, word in enumerate(words):
                    
                    try: tmp_word = word[:i] + word[i+1:]
                    except: tmp_word = word[:i]
                    
                    if tmp_now == tmp_word and visited[w] == 0:
                        visited[w] = 1 
                        queue.append((word, c + 1))
        return 0

now는 현재 단어, c는 변경 횟수이다. 만약 now가 target 단어가 되면 c를 반환한다.

아니라면, now와 target의 값이 다른 인덱스 하나를 찾아서 바꿀 수 있는 경우를 queue에 append한다. (바꿀 수 있는 경우 = now에서 한 문자만 변경한 문자가 words 안에 있는지 검사)  만약 바꿀 수 있는 단어가 이전에 변경했던 단어라면 queue에 추가하지 않는다. 

더이상 queue에 값이 없는데 target이 되지 않았다면 0을 반환해준다.

 

try-except 문은 i(인덱스)가 마지막인 경우 [i+1:] 슬라이스를 해주면 인덱스 에러가 뜨기 때문에 해주었다.

전체 코드

from collections import deque

def solution(begin, target, words):
    visited = [0 for _ in range(len(words))]
    
    def bfs(begin, target, words, visited):
        queue = deque([(begin, 0)])
        
        while queue:
            now, c = queue.popleft()
            
            if now == target: 
                return c
            
            for i in range(len(target)):
                if now[i] == target[i]:
                    continue
                    
                try: tmp_now = now[:i] + now[i+1:]
                except: tmp_now = now[:i]
                
                for w, word in enumerate(words):
                    
                    try: tmp_word = word[:i] + word[i+1:]
                    except: tmp_word = word[:i]
                    
                    if tmp_now == tmp_word and visited[w] == 0:
                        visited[w] = 1 
                        queue.append((word, c + 1))
        return 0
            
    
    return bfs(begin, target, words, visited)