단어 변환 Pgs#43163

단어 변환 PGs#43163

Python 코드 보기

import copy
answer = 99

def check(origin, dest, target):  # 1가지 글자만 달라지는 경우
    change = 0
    
    for i in range(0,len(origin)):
        if origin[i] != dest[i]:
            change += 1
        if change > 1:
            return 0
    if change == 1:
        # print(origin, "->", dest,", target:", target)
        return 1
    
def dfs(begin, target, words, count):
    global answer
    count += 1
    if words == []:                     # word가 더 없는 기저사례
        return
    
    for nextWord in words:
        if check(begin, nextWord, target):
            if nextWord == target:      # 원하는 단어 완성
                answer = min(answer, count)
                return
            nextWords = copy.copy(words)
            nextWords.remove(nextWord)
            dfs(nextWord, target, nextWords, count)
    
def solution(begin, target, words):
    global answer
    words.sort()
    
    dfs(begin, target, words, 0)
    
    if answer > 50:
        return 0
    return answer

---

☝ 입력 형식

두 개의 단어 begin, target과 단어의 집합 words가 있습니다.

아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

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

• 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어진다.

🤞 출력 형식

• 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

🤟 구현 과정

1. 1가지 문자만 달라지는 경우를 검색 : check()

• check()함수는 현재 단어와 다음 단어가 1가지 문자만 다른 경우 True를, 그 외의 경우는 False를 반환하는 함수다.

2. dfs를 통해 반복

• dfs를 통해 target에 도달하였는가 검색함.
  • words배열이 완전히 비었을 경우, 기저사례로 return함.
  • check()함수가 True인 경우
    • 다음 단어가 target인 경우, count를 answer과 비교하여, 더 작은 값을 answer에 기록하고, return함.
    • 다음 단어를 begin으로 하는 dfs를 반복함.