[Programmers] 단어 변환

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

프로그래머스

 

접근 방법

문제를 읽다보면, 구현 같지만 구현과 BFS/DFS 알고리즘이 혼합된 것 같다.

문제 속에서 '최소 몇 단계' 라는 말이 있었기 때문에 BFS로 접근하면 되겠구나 생각이 들었다.

BFS는 최단거리가 보장되는 경로를 탐색할 수 있기 때문이다.

 

그래서 코드 작성하기 전 과정을 적어보면 다음과 같이 풀 수 있다.

  '''
    최소 단계를 거쳐 begin -> target으로 변환
    변환할 때 마다 count + 1
    hit -> cog 로 갈 수 있는 최소 변경 횟수
    graph : hot -> dot 으로 1개씩 변경된다면, 인접리스트로 추가
    hit에서 h가 바뀔때, _it가 words에 있는지 확인 => 없으면, 패스
    hit에서 i가 바뀔때, h_t가 wrords에 있는지 확인, hot, ->있으면 queue에 추가, visited[hot] = True
    hit에서 t가 바뀔때, hi_가 words에 있는지 확인, -> 없으면, 패스
    
    queue .popleft()
    
    hot에서 h가 바뀔때, _ot 있는지 확인, dot, lot -> queue에 추가 (dot, lot) , visited = ture
    hot에서 o가 바뀔때, h_t가 있는지 확인, 업승면 패스
    hot에서 t가 바뀔때, ho가 있는지 확인, (+not visited  여야함) 없으면 패스
    
    queue = (dot, lot)
    queue.popleft
    ... 반복
    -> target 찾으면 종료., 못찾으면 0 리턴
    '''

이걸 그대로 코드로 구현하면 된다.

 

풀이

from collections import deque
def solution(begin, target, words):
  
    visited = {}
    answer = {}
    for w in words:
        visited[w] = False
        answer[w] = 1
    queue = deque()
    queue.append(begin)
    answer[begin] = 0
    
    while queue:
        begin_w = queue.popleft()  
        if begin_w == target:
            return answer[target]
        for i in range(len(begin_w)):
            tmp = begin_w[:i] + begin_w[i+1:]
            for w in words:
                if (w[:i] + w[i+1:]) == tmp and not visited[w]:    # 1개 알파벳 변경할 수 있다면, queue에 추가
                    queue.append(w)
                    answer[w] += answer[begin_w]
                    visited[w] = True
    
    return 0