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

단어변환

문제

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

풀이

백트래킹

input이 크지 않기 때문에 백트래킹으로 풀 수 있다.

사용한 단어를 체크한 다음에 재귀가 끝나면 다시 초기화 해줘야하는데 안해줘서 헤맸다.

가능한 모든 조합을 찾은 뒤 depth가 최소인 것으로 cnt를 업데이트 해서 리턴해줬다.

def possible(begin, word): # 한 번에 알파벳 한 개만 바꿀 수 있음
    cnt = 0
    for c1, c2 in zip(begin, word):
        if c1 == c2:
            cnt += 1
    return len(begin) - cnt == 1 
​
def change(begin, target, words, depth, checked):
    if begin == target: # 변환 끝났으면 재귀 종료
        return depth
      
    cnt = len(words) # 최댓값으로 초기화
    
    for i, word in enumerate(words):
        if not checked[i] and possible(begin, word):# 사용하지 않았고, 변환 가능한 단어일 때
            checked[i] = True # 사용한 단어 표시
            cnt = min(cnt, change(word, target, words, depth + 1, checked))
            checked[i] = False # 사용한 단어 표시 지우기
    return cnt
​
def solution(begin, target, words):
    answer = 0
    checked = [False] * len(words)
    
    if target not in words: # 변환할 수 없는 경우 가지치기
        return 0
    
    return change(begin, target, words, 0, checked)

bfs

큐에 변환횟수, 현재 단어 넣고 BFS

• 큐에 남은 게 없을 때까지 하나씩 꺼내서 만약 현재 단어가 target이면 변환횟수 리턴
• 변환 가능한 단어를 찾아서 checked에 표시하고 횟수 +1, 단어 큐에 넣기

from collections import deque
​
def possible(cur, word):
    cnt = 0
    for c1, c2 in zip(cur, word):
        if c1 != c2:
            cnt += 1
    return cnt == 1
​
def solution(begin, target, words):
    answer = 0
    
    if target not in words:
        return 0
    
    checked = [False] * len(words)
    
    q = deque()
    q.append((0, begin))
    
    while q:
        cnt, cur = q.popleft()
        if cur == target:
            return cnt 
        
        for i, word in enumerate(words):
            if not checked[i] and possible(cur, word):
                checked[i] = True
                q.append((cnt + 1, word))
    
    return 0