[프로그래머스] 단어변환

1. 문제

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

프로그래머스

 

 

2. 풀이

그림으로 재현하자면 약간 이런느낌입니다.

 

최단거리니까 역시 BFS로 구현하는데,

1. 만약 target 단어가 words 안에 없으면 그건 안되는 거라 0 반환

2. word안에서 연결리스트로 그래프 딕셔너리 생성하기

3. 생성 기반으로 bfs돌려서 최단거리 확인하기

 

BFS 문제를 하도 풀다보니까 이젠 간편하다,,

 

## code ##

import collections
def solution(begin, target, words):
    answer = 0
    
    def bfs(visited):
        stack = collections.deque([begin])
        cnt = 0
        
        while stack:
            c = stack.popleft()
            
            if c == target:
                return visited[c]
                
            for w in graph[c]:
                if w not in visited.keys():
                    stack.append(w)
                    visited[w] = visited[c] + 1
                    
    if target not in words:
        return 0
    
    words.append(begin)
    graph = collections.defaultdict(list)
                                    
    for word in words:
        for word2 in words:
            if word == word2: continue
            if len([x for i, x in enumerate(word) if x != word2[i]]) == 1:
                graph[word].append(word2)

    visited = collections.defaultdict(int)
    visited[begin] = 0
    end = bfs(visited)
    if end is None:
        end = 0
        
    return end