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

문제

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

프로그래머스

 

BFS로 간단하게 풀어보자!

---

 

주요 아이디어

• 가장 짧은 변환 과정 -> 최단 경로 -> BFS를 떠올려야 한다
• begin을 queue에 넣고 시작
• 하나씩 popleft() 하면서 순회
  • visited에 방문 처리
  • 한 글자가 다른 단어로만 변환 가능하므로, 인접 노드는 한 글자만 다른 것들 넣기
  • 최단 경로이므로 target과 가장 가까운 순서대로 pop해야 함
  • 변환 안될 경우 0을 반환해서 예외처리 해주기

 

 

---

 

코드 구현 (Python 3)

 

from collections import deque

# 단어 2개가 몇 개 알파벳 일치하는지 개수 반환
def word_check(word, now):
    cnt = 0
    for idx in range(len(word)):
        if word[idx] == now[idx]:
            cnt += 1
    return cnt

def solution(begin, target, words):
    answer = -1
    visited = []
    
    queue = deque()
    queue.append(begin)
    
    while queue:
        # 뽑기 전에 sort 해야 함
        # target이랑 가장 가까운 순서로 돌아야 하므로, target과 글자 차이 가장 적은 순으로 정렬
        queue = deque(sorted(queue, key=lambda x: word_check(x, target), reverse=True))
        now = queue.popleft()
        
        visited.append(now) # 방문 처리
        answer += 1 # path append
        if now == target:
            break
        
        # 알파벳 현재꺼랑 하나만 다른 것들 & 방문 안한 것들
        adj = [x for x in words if word_check(x, now) == len(now)-1 and x not in visited]
        
        for adj_word in adj:
            if adj_word not in queue:
                queue.append(adj_word)
    
    # 모두 방문했음에도 target으로의 변환이 불가능한 경우
    if now != target:
        return 0
    else:
        return answer

 

 

---

 

제출 결과