[파이썬] 프로그래머스 : 단어 변환 (Lv.2)

[파이썬] 프로그래머스 : 단어 변환 (Lv.2)

 

프로그래머스

 

---

풀이

0. 방향성 생각

시작단어를 words에 넣어놓고 이동 가능한 경로를 table 딕셔너리에 저장 후 거리 visit 딕셔너리도 만들기

무방향 그래프이므로 둘 다 추가해주기.

target 단어 유무로 완성 유무 판별. 탐색이 가능한 경우에만 탐색

 

전체코드

from itertools import combinations as C
from collections import deque

def solution(begin,target,words):
    
    words = set(words)
    words.add(begin)
    table = {word : [] for word in words}
    visit = {word : -1 for word in words}
    
    if target not in words :
        return 0
    else:
        temp = list(C(words,2))
        for a,b in temp:
            count = 0
            for x,y in zip(a,b):
                if x!=y : count +=1
            if count == 1:
                table[a].append(b)
                table[b].append(a)
                
        q = deque([begin])
        visit[begin] = 0
        
        while q:          
            x = q.popleft()
            if x == target : break
            
            if table[x]:
                for nx in table[x]:
                    if visit[nx] == -1:
                        q.append(nx)
                        visit[nx] = visit[x]+1
        if target in table:
            return visit[target]