title: "[프로그래머스] 단어 변환 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/43163"
description: "프로그래머스 Level 3 문제 [단어 변환]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

import itertools
from collections import defaultdict, deque

def hamming(w1, w2):
    return sum(c1 != c2 for c1, c2 in zip(w1, w2))

def solution(begin, target, words):
    A = defaultdict(list)
    for w1, w2 in itertools.combinations(words + [begin], 2):
        if hamming(w1, w2) == 1:
            A[w1].append(w2)
            A[w2].append(w1)
    
    q, vis = deque(), set()
    q.append((begin, 0))
    vis.add(begin)
    while len(q) > 0:
        word, d = q.popleft()
        if word == target:
            return d
        
        for v in A[word]:
            if v not in vis:
                q.append((v, d+1))
                vis.add(v)
    
    return 0

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges