Level 3 단어 변환 Python3

https://programmers.co.kr/learn/courses/30/lessons/43163?language=python3# 

코딩테스트 연습 - 단어 변환

 

최종 풀이

• GitHub https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_단어변환.py

hwayeon351/Programmers-Algorithms

def dfs(i, target, words, visit, cnt):
    global answer
    if words[i] == target:
        if answer == 0 or answer > cnt: answer = cnt
        return
    if cnt == len(visit)-1: return
    for b_i in range(len(words[i])):
        for idx, w in enumerate(words):
            if words[i][:b_i]==w[:b_i] and words[i][b_i+1:]==w[b_i+1:] and visit[idx]==False:
                visit[idx] = True
                dfs(idx, target, words, visit, cnt+1)
                visit[idx] = False

def solution(begin, target, words):
    global answer
    if target not in words: return 0
    answer = 0
    words.append(begin)
    visit = [False]*len(words)
    visit[-1] = True
    dfs(-1, target, words, visit, 0)
    
    return answer

---

풀이 과정

풀이 시간 1시간 3분

바꿀 수 있는 단어를 찾아 계속해서 바꿔나가면서 tartget과 같은 단어를 만들고, 그 때 바뀐 횟수가 가장 작은 것을 return하는 문제이다.

즉, 예제 1번의 경우 hit->hot->dot->dog->cog인 경우가 4번으로 가장 짧지만, hit->hot->dot->hot->dot->dog->cog 이런식으로 앞전의 단어를 반복적으로 바꿔서 target을 만드는 경우의 수도 생길 수 있다.

이 경우 무한 루프가 생길 수도 있기 때문에 DFS 알고리즘을 적용해서 visit 배열을 통해 이전에 바꿨던 단어이면 반복적으로 바꾸지 않도록 구현했다.

문제에서 words의 수는 최대 50개이고 단어의 길이는 최대 10이기 때문에 DFS 알고리즘으로 탐색하더라도 10*50*50 = 25000번 조건문이 실행되어 시간초과가 나지 않음을 확인할 수 있다.

 

• target이 words에 들어있지 않는 경우, 단어 변환이 불가능하므로 return 0을 해준다.
• target이 words에 들어있는 경우, 

1. answer = 0으로 초기화 하고, begin을 words에 추가하고 words의 길이만큼 visit 배열을 만든다. begin은 마지막 인덱스를 가리키므로 visit[-1] = True로 바꿔준다. begin 인덱스인 -1과 cnt를 0을 매개변수로 하여 dfs 함수를 호출한다.
2. DFS의 시작 노드를 찾기 위해 한 글자만 바꿀 수 있는 단어를 찾는다. begin의 각각의 인덱스가 바뀌는 글자라고 생각하고 나머지 글자가 같은지를 확인하면 된다.
3. 바꿀 수 있는 단어를 찾으면 visit[idx] = True, cnt+1를 하고 dfs 함수를 호출한다.
4. dfs 함수 내에서도 2. 3.과정을 수행하며 target 단어로 바뀌었는지 계속해서 체크하고, target 단어와 같은 경우 answer 값과 cnt를 비교하여 더 작은 값으로 answer 값을 바꿔준다.