[ Programmers 43163 ] 단어 변환(Python)

문제

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

시작 단어에서 타겟 단어까지 한글자씩만 변화할 때 가장 짧은 변환 과정을 찾는 문제이다.
변환할 수 없는 경우에는 0을 리턴하면 된다.

문제 풀이

1. 타겟 단어가 단어의 집합인 words에 없으면 0을 리턴하는 예외 처리를 해준다.
2. 만약 현재 단어 word가 타겟 단어와 같으면 depth를 리턴해준다.
3. 현재 단어 word 와 비교할 단어 w가 한글자만 다른지 체크하는 함수 compare 값이 1이고, 비교할 단어를 방문하지 않았으면 방문 체크를 해준다.
4. depth를 1 더하고, 비교한 단어를 dfs 함수로 넣어준다.
   ➣ dfs(depth+1, w)
   4-1. 모든 단어와 비교를 했으면, dfs(depth+1, w) 의 리턴값 이 있는지 체크해준다.
   4-2. 리턴값이 없으면 임의의 큰 값인 max_int가 ret에 할당된다.
5. 비교 단어 w 에 대한 방문 해제 해준다.
6. dfs가 끝난 후 리턴값이 max_int와 같으면 타겟 단어로 변환이 되지 않았다는 뜻이므로 0을 리턴한다.

코드

import sys
MAX_INT = 52372727
def compare(s1,s2):
    cnt = 0
    for i in range(len(s1)):
        if s1[i]!=s2[i]:
            cnt+=1
            if cnt==2 : return False
    return True

def solution(begin, target, words):
    visited = [0] * len(words)
    if target not in words : return 0

    def dfs(depth,word):
        if word == target: return depth

        ret = MAX_INT
        for i,w in enumerate(words):
            if compare(word,w) and visited[i]==0:
                visited[i]=1 
                ret = min(ret, dfs(depth+1, w))
                visited[i]=0 
        return ret
        

    ret = dfs(0,begin)

    if ret == MAX_INT:
        return 0
    else:
        return ret