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

1. 문제 

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

프로그래머스

 

2. 알고리즘 

1. 바꿔보고 돌리고 하는 백트래킹 사용

2. 먼저 한글자만 다른지 확인하는 함수 checker 구현  -> 문자열 전체길이 -1 이 같은 글자 수 인지 확인

3. dfs로 순회해주는데 생각할 조건은 최소값을 구해야하므로, 종료 조건의 경우 현재 문자열이 target과 같아질때 min 으로 업데이트 해준다

4. words를 돌면서 checker로 한글자만 다르고 방문한 적 없는지 확인하여 순회한다

5. words 에 target이 없으면 아예 연산이 불가하니 바로 0 반환 

6. 함수를 다 돌고 나왔는데 여전히 ans 가 51이면 만들수 없다는 의미이므로 0 반환

 

3. 코드 

ans = 51 # 최댓값 설정 50개 이하의 단어만 연산 하므로 
def checker(a,b): # 한 글자만 다른지 체크 하는 함수 
    len_a, len_b = len(a), len(b)
    cnt = 0 
    for x,y in zip(a,b):
        if x == y: 
            cnt +=1 
    if cnt == len_a -1: #한글자만 다른 경우 
        return True
    else: 
        return False
                                  
def solution(begin, target, words):
    global ans
    if target not in words: # target이 변환 대상에 없는 경우 불가 return 0
        return 0
    
    visited = [False] * (len(words))
    
    def dfs(cur, move):
        # print(f"cur: {cur} move:{move}")
        global ans
        if cur == target: #종료조건 target을 만든 경우 
            ans = min(ans, move) #최소한의 변환으로 
            return 
        
        for i in range(len(words)): 
            if not visited[i] and checker(cur, words[i]): #방문한 적 없으며 한글자만 다르다면
                visited[i]=True #방문 
                dfs(words[i], move+1) #dfs로 확인
                visited[i]=False #되돌리기
                
    dfs(begin, 0) 
    if ans == 51: #다 확인했는데 변환 안되는 경우 0
        return 0
    return ans