[Programmers] 단어 변환 (DFS/BFS Lv.3) - Python

1. 문제

---

단어 변환

2. 풀이

---

코드

from collections import deque

def solution(begin, target, words):
    visited = [False] * len(words)
    queue = deque([(begin, 0)])
    while queue:
        current, count = queue.popleft()
        if current == target:
            return count
        for i, word in enumerate(words):
            if not visited[i] and is_adjacent(current, word):
                queue.append((word, count + 1))
                visited[i] = True
    return 0

def is_adjacent(word1, word2):
    diff_count = 0
    for char1, char2 in zip(word1, word2):
        if char1 != char2:
            diff_count += 1
    if diff_count == 1:
        return True
    return False

입력 및 출력

begin = "hit"
target = "cog"	
words = ["hot", "dot", "dog", "lot", "log", "cog"]

>> 4

3. 로직

---

1. 주어진 단어 리스트(words)에서 변환을 할 수 있는 단어들로만 이루어진 큐(queue)와 방문 여부를 저장하는 리스트(visited)를 생성한다.

2. 큐(queue)에 시작 단어(begin)와 변환 횟수 0을 넣어 초기화한다.

3. 큐(queue)가 비어있을 때까지 반복한다.

4. 큐(queue)에서 가장 왼쪽의 단어(current)와 해당 단어까지의 변환 횟수(count)를 가져온다.

5. 현재 단어(current)가 목표 단어(target)와 동일한 경우, 현재까지의 변환 횟수(count)를 반환한다. (단어 변환이 완료된 경우)

6. 주어진 단어 리스트(words)에서 아직 방문하지 않은 단어들 중에서 현재 단어(current)와 한 글자만 다른 단어들을 찾습는다.

7. 해당 단어들을 큐(queue)에 추가하고, 변환 횟수(count)를 1 증가시킨다.

8. 추가한 단어들은 방문 여부를 표시하기 위해 visited 리스트의 해당 인덱스를 True로 변경한다.

9. 변환을 할 수 있는 단어를 모두 큐(queue)에 추가하고 방문 여부를 업데이트한 후, 다시 4번부터 반복한다.

10. 큐(queue)가 비어있고 목표 단어(target)에 도달하지 못한 경우, 변환할 수 없으므로 0을 반환한다.

4. 그림

---