[프로그래머스] 단어 변환

문제

• begin 단어를 target 단어로 변환하는 가장 짧은 변환 과정 찾기
• 변환 규칙은 다음과 같다.
  • 한 번에 한 개의 알파벳만 바꿀 수 있다.
  • 주어진 words 속의 단어로만 변환할 수 있다.
• 3 <= (단어의 길이) <= 10
• 3 <= len(words) <= 50
• 변환할 수 없는 경우에는 0 리턴하기

 

풀이

• words 내에 target이 없다면 변환 불가능한 경우이므로 0 리턴하기
• 반복적으로 words 내 각 단어를 돌면서 변환할 수 있는지 확인하고 한 알파벳씩 변환하기
  • 바꿔야할 인덱스를 구한 뒤, 모든 인덱스가 변환될 때까지 반복한다.
  • 알파벳 하나만 다른 단어를 찾고, 변환한 다음 큐에 추가하기
  • 만약 바꾼 알파벳이 target과 동일하다면 바꿔야할 인덱스에서 제외하기

 

from collections import deque

def solution(begin, target, words):
    words_set = set()       
    n = len(begin)          # begin 문자열의 길이
    # words 문자열 중 길이가 n인 문자열만 set으로 저장
    for i in range(len(words)):
        if len(words[i]) == n :
            words_set.add(words[i])
    
    # words 안에 target이 없다면 목표 도달 불가능
    if target not in words_set :
        return 0
    
    # 바꿔야할 인덱스 번호 저장
    visited = set()     
    for i in range(n):
        if begin[i] != target[i] :
            visited.add(i)
            
    # (문자열, 변환횟수, 바꿔야할 인덱스들, 바꿀 수 있는 단어 집합)
    q = deque([(begin, 0, visited, words_set)])  
    answer = int(1e9)
    
    while q:
        now, cnt, visited, words = q.pop()
        
        if now == target :  # 목표 도달한 경우
            answer = min(answer, cnt)
            continue
        
        if cnt >= answer :  # 문자열 비교가 끝났거나, 최솟값이 아닌 경우
            continue
            
        for w in words:         # 바꿀 수 있는 단어별로
            for i in visited:   # 그 중 바꿔야하는 인덱스 순으로 확인
                # w가 타겟과 i번째 문자가 같고, i번째를 제외하고는 현재 문자열과 같은 경우
                if now == w[:i]+now[i]+w[i+1:] :
                    if w[i] == target[i] :  
                        # 만약 target 하고 같으면 바꿔야 하는 인덱스 삭제
                        q.append((w, cnt+1, visited-set([i]), words-set([w])))
                    else:
                        q.append((w, cnt+1, visited, words-set([w])))
                    
    
    if answer == int(1e9) :
        return 0
    return answer

 

References

• 프로그래머스 고득점Kit BFS/DFS