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

일주일전에 풀었는데 안풀려서 방치해뒀다가 그 다음주 주말에 풀었더니 풀렸다.. 아휴ㅠ^ㅠ

 

풀이 과정

begin 에서 target으로 글자를 하나씩만 변경해서 가장 적은 단계로 변경하는 알고리즘 구현하기

0. hit -> cog 로 변경한다면 (그림 그려봤는데 DFS가 제일 먼저 떠오름)

 

1. words를 뒤져서 하나만 다른 경우를 탐색한다.

•  - 예시의 글자가 3글자라서 2개가 다른 경우로 했더니 테스트케이스에서 틀림
•  제한사항에 분명히 <각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.> 라고 명시되어있음
•  전체 글자수 - 같은 글자수 = 1 인 경우로 조건을 바꾸니 테스트케이스 통과함

2. 한번 탐색한건 체크해서 탐색하지 않는다.

3. target 값이 나오면 L을 출력한다.

•  가장 최단거리 L을 찾아야함으로 최소값을 출력해준다.

4.체크하고 DFS에서 탐색실패로 return 되면 백트래킹 해줘야함. 

 

 

코드

import sys

def DFS(L,val,ch,begin,target, words):
    global answer
    if val==target:
        if answer> L:
            answer = L
            return
    else:
        for idx,k in enumerate(words):
            if ch[idx]==0:
                cnt=0
                for i in range(len(val)):
                        if val[i]==k[i]:
                            cnt+=1
                if len(val)-cnt ==1:
                        ch[idx]=1
                        DFS(L+1,k,ch,begin, target, words)
                        ch[idx]=0
                                                           
def solution(begin, target, words):
    global answer
    ch=[0]*len(words)
    if target in words:
       DFS(0,begin,ch, begin, target, words)
    else:
        answer = 0
    return answer

if __name__ == "__main__":
    answer = 2167000000        
    print(solution("hit","cog",["cog", "log", "lot", "dog", "dot", "hot"]))#4
    #print(solution("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"])) #4
    #print(solution("hit", "cog", ["hot", "dot", "dog", "lot", "log"])) #0    
    #print(solution("hit", "hot", ["hot", "dot", "dog", "lot", "log"])) #1
    #print(solution("1234567000", "1234567899", ["1234567800", "1234567890", "1234567899"])) #3
    print(solution("hit", "cog", ["cog", "log", "lot", "dog", "hot"])) #4