[Python] Programmers 단어 변환

1. 문제 링크

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

코딩테스트 연습 - 단어 변환

---

2. 문제 요약

한 번에 한 개의 단어만 변경하여 begin ⇒ target으로 변경하는 최소의 과정 찾기

---

3. 아이디어 정리

• bfs로 현재 단어에서 변경 가능한 값을 방문하는 방식을 이용합니다.

1. 현재 값이 target과 동일하면 그만
2. 모든 단어를 현재 단어와 비교하여 1개 차이나는 경우 deque에 넣어서 방문하도록 한다.

---

4. 문제 풀이

4-1. 내 풀이

from collections import deque

def solution(begin, target, words):
    dq = deque([(begin, 0)])
    visit = [False] * len(words)

    while dq:
        now, count = dq.popleft()
        if now == target:   # target과 동일하면 현재 단계 리턴 
            return count
        # 모든 단어 확인하면서 1개 차이나는 것 찾기 
        for i, word in enumerate(words):
            if visit[i]:   # 방문한 경우 그만 
                continue
            if len([i for i, w in enumerate(word) if now[i] != w ]) == 1:
                dq.append((word, count + 1))
                visit[i] = True
    return 0  # 변환 불가능한 경우

 

---

5. 결론

• bfs를 활용하여 begin 값에 너비 우선 탐색을 하는 문제