단어 변환

📖 깊이/너비 우선 탐색(DFS/BFS)

📖What I thought

1. 일단 타겟이 단어 모음에 없으면 불가능
2. 한 글자 씩만 바꿀 수 있으니까 앞 단어에서 한 글자만 다른 애들이 같은 depth → depth도 단어랑 같이 저장해주기
3. 쭉쭉 타고와서 타켓 단어 도달하깅
4. 도달했을 때 depth 젤 작은 경우가 가장 짧은 변환 과정
5. depth와 최단 경로??? 고러면 bfs로 샤삿 돌아보면 될 듯

📖풀이

📎BFS

from collections import deque
 
# BFS
def bfs(begin, target, words):
    cnt = 50
    
    q = deque([(begin,0)]) # (단어, 변환횟수)
    v = {word: False for word in words}
    
    while q:
        now, dep = q.popleft()
        v[now] = True
        
        # target 단어 도달
        if now == target:
            cnt = min(cnt, dep)
        
        # 한 알파벳만 다른 단어 찾기
        for word in words:
            diff = 0
            
            # 이미 지나온 단어 패스
            if v[word]:
                continue
                
            for n, w in zip(now, word):
                if n != w:
                    diff += 1
            
            # 한 알파벳만 다른 단어인 경우
            if diff == 1:
                q.append([word, dep+1])
    
    return cnt
 
# main
def solution(begin, target, words):
    # target 단어가 아예 없을 경우
    if target not in words:
        return 0
    
    return bfs(begin, target, words)

📖What I learned

1. 경로!! 하면 DFS/BFS 기억하기 ⭐️ 그 중에서도 최단 경로, depth를 이용한 경로는 BFS를 바로 떠올리자
2. zip으로 각 시퀀스 묶어서 새로운 iterable 자료형 만드는 것 뿐만 아니라 이렇게 같은 idx의 값 비교도 가능했다 ⭐️ 같은 길이의 단어라서 가능했음, 길이 다르면 더 긴 자료형의 나머지 요소들은 사용되지 않음

📖관련 지식

📎BFS(Breadth-First Search)

📎Dictionary Comprehension

📎zip