[코딩테스트] 프로그래머스 - 단어 변환

1. 아이디어 

▪ 단어를 입력받은 단어로 변환할 수 있는지 확인하는 함수 작성 

   - for 문 돌리면서 한 글자씩 제거하고 비교했을때 같으면 True, 다르면 False

▪ target이 words에 포함되어 있지 않으면 0 return 

▪ target이 words에 포함되어 있으면 dfs 

▪ dfs

   - begin과 target이 같으면 결과리스트에 단계수 append 

   - 아니면 for문으로 변환 가능한 단어 찾고 방문하지 않았을 경우 

      - 방문여부 리스트에 추가

      - answer += 1 하고 변환한 단어로 dfs

      - 방문여부 리스트에서 제거

2. 시간복잡도

▪ O(V+E) = O(V+V*10) 

3. 변수

▪ 방문여부 리스트: str[]

▪ 변환 단계수 저장할 리스트: int[]

Code

def change(word, c_word):
    for i in range(len(word)):
        if word[:i]+word[i+1:] == c_word[:i]+c_word[i+1:]:
            return True

    return False

def solution(begin, target, words):   
    def dfs(begin, target, answer):        
        if begin == target:
            rs.append(answer)
            return 

        else:
            for word in words:
                if change(begin, word) and word not in chk:
                    chk.append(word)
                    dfs(word, target, answer+1)
                    chk.pop()
                    
    chk = []
    rs = []
    
    if target not in words:
        answer = 0 
    
    else:
        dfs(begin, target, 0)
        answer = min(rs)
    
    return answer

 

프로그래머스