[programmers] 단어 변환

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

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

 

• 알고리즘을 최근 3일정도 풀지 않았더니 감이 슬슬 떨어지고 있는 것 같아 기본적인 dfs/bfs 문제를 풀어봤습니다.
• '가장 짧은 변환 과정' 이라는 조건을 보고 BFS를 써야된다고 생각했고, 자세한 설명은 주석을 참고해주시면 감사하겠습니다.

 

from collections import deque    

# 한 번에 한개의 알파벳만 바꿀 수 있다는 조건 구현
def check(word,diff_word):
    cnt = 0
    # zip을 이용해서 짝을 맞추고 각각 단어를 비교한뒤
    for w1,w2 in zip(word,diff_word):
        # 다른 알파벳개수를 return
        if w1 != w2:
            cnt += 1
    return cnt

def solution(begin, target, words):
    # words를 인덱스로 활용, visited 체크 리스트 생성
    visited = [0 for _ in range(len(words))]
    answer = 0
    
    q = deque()
    q.append((begin,0))
    while q:
        # 비교할 단어와 cnt 추출
        word,cnt = q.popleft()
        # 비교할 단어가 target과 같으면 비교할 단어의 cnt값을 answer로 지정
        if word == target:
            answer = cnt
            break
        # 조건을 보면 words에 있는 단어로만 변환
        # words[i] 를 for문으로 해결
        for i in range(len(words)):
            tmp = 0
            if visited[i] == 0:
                # 체크 안되어있을 때 check함수가 1일 때(틀린알파벳이 1개일 때)
                if check(word,words[i]) == 1:
                    q.append((words[i],cnt+1))
                    visited[i] = 1
    return answer