[ 알고리즘 ] BFS 문제 - 단어 변환

 

문제)

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 

"hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

코드)

from collections import deque

def is_one_letter_diff(word1, word2):
    # 두 단어가 한 글자만 다른지 확인하는 함수
    diff_count = 0
    
    for c1, c2 in zip(word1, word2):
        if c1 != c2:
            diff_count += 1
        if diff_count > 1:
            return False
    return diff_count == 1

def solution(begin, target, words):
    # words 안에 target 단어가 있는지 먼저 확인. 없으면 0 return 한다.
    if target not in words:
        return 0

    # 만약 words 안에 target 단어 있으면 BFS 준비
    queue = deque([(begin, 0)])  # (현재 단어, 변환 횟수)
    visited = set()  # 방문한 단어를 기록

    while queue:
        current_word, step = queue.popleft()
        if current_word == target:
            return step

        for word in words:
            if word not in visited and is_one_letter_diff(current_word, word):
                visited.add(word)
                queue.append((word, step + 1))

    return 0

 

• return diff_count==1 대신 return True 라고 해도 된다. (-> 일단 테스트는 통과됨.) 하지만 모든 글자가 같은 경우가 제외되기 때문에 조심해야한다. 하지만 if currend_word == target  모든 글자가 같은 경우는 걸러서 테스트 통과에 상관이 없는 걸로 예상한다... 내생각..ㅋㅋ
• 여기서 set()과 add() 대신 list()과 append()를 사용해도 된다. 하지만 요소들의 순서를 고려해야 하는 상황이 아니기 때문에 list 말고 set을 사용했다. 그리고 많은 데이터 속에서 in 연산자를 사용하는 경우일 때, list 보다 빠르다. 시간 복잡도면에서 set은 O(1)이고 , list는 O(n)이다.

 

 

해석)

• queue에 추가되는 요소는 (word, step + 1) 형식이다. 여기서 word는 조건을 만족하는 다음 단계의 단어를, step + 1은 현재 단계에서 다음 단계로 넘어갈 때 변환 횟수를 1 증가시킨 값을 의미한다.
• is_one_letter_diff 함수는 비교하는 두 단어에서 한 글자만이 다른지 확인한다. 만약 current_word == target이면 step(변환 횟수)을 return 하고, 함수는 즉시 종료된다.

 

zip() 함수 : 여러 개의 순회 가능한(iterable) 객체를 인자로 받고, 각 객체가 담고 있는 원소를 튜플의 형태로 차례로 접근할 수 있는 반복자(iterator)를 반환한다. zip 함수의 결과를 직접 보고 싶다면 이터레이터를 리스트나 튜플로 변환한 후 출력해야 한다.

list1 = [1, 2, 3]
list2 = ['a', 'b', 'c']

zipped = zip(list1, list2)
print(list(zipped))

# 결과
[(1, 'a'), (2, 'b'), (3, 'c')]