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

문제

begin으로 주어진 단어에서 시작해 target 단어를 만드려고 한다. words에 주어진 단어 리스트를 사용해 target 단어로 변환할 수 있는데, 한 번에 알파벳이 1개만 다른 단어로 변환할 수 있다. 가장 짧은 변환 과정은?
(문제 링크)

 

내 풀이

• BFS로 풀이했으며 deque 라이브러리로 큐를 사용했다.
• words에 존재하지 않아 변환할 수 없는 단어는 0을 반환한다.
• (시작 단어, 0)을 queue에 넣는다.
• queue 요소를 하나 꺼내고, 꺼낸 단어와 1글자만 다른 단어를 큐에 삽입한다. 정답 단어를 찾으면 반환하고, 찾지 못하면 계속 반복한다.

from collections import deque

# 한 글자만 다른 단어인지 확인
def is_valid(word, target):
    same = 0
    for i in range(len(word)):
        if word[i] == target[i]:
            same += 1
    if same == (len(word) - 1):
        return True
    return False

# 위와 동일한 기능의 함수
def is_valid2(word, target):
    diff = 0
    for i in range(len(word)):
        if word[i] != target[i]:
            diff += 1
    if diff == 1:
        return True
    return False

위의 두 함수는 word, target 단어가 1글자만 차이나는 단어인지 확인하는 함수이다. 1글자만 차이나는 단어를 유효한 단어라고 표현하겠다.

 

첫 번째 is_valid()은 두 단어에서 동일한 글자 개수를 세어 유효한 단어인지 판별하고, is_valid2()는 두 단어에서 다른 글자 개수를 세어 유효한 단어인지 판별한다. 둘 다 동일한 기능을 하는 함수이지만, 첫 번째 함수를 짤 때 조금 헷갈렸기 때문에 두 번째 함수도 만들어보았다.

 

# BFS 풀이
def solution(begin, target, words):
    # 변환할 수 없는 단어인 경우
    if target not in words:
        return 0
    
    # 큐에 현재 단어와 1글자 차이나는 단어 넣기
    queue = deque()
    queue.append([begin, 0])

    while queue:
        word, cnt = queue.popleft()

        if word == target:
            return cnt

        # 변환할 수 있는 단어 모두 큐에 넣기
        for i in range(len(words)):
            if is_valid(words[i], word):
                queue.append([words[i], cnt+1])
    
    return 0

위에서 선언한 유효한 단어인지 확인하는 is_valid()를 활용해 가장 짧은 변환 과정을 찾는다.

 

이 문제는 테케 3만 조금 오래 걸리고, 다른 테스트케이스는 복잡하고 길지 않아서 모두 통과했다. 실행 시간 단축을 위해 코드를 개선했습니다.

 

개선한 풀이

첫 번째 풀이의 경우, 한 번 사용한 단어를 다시 사용할 수 있습니다.(큐에 넣을 수 있습니다) 이미 사용한 단어를 또 사용하며 시간이 오래 걸리기 때문에 사용(방문) 여부를 표시하기 위해 visited 딕셔너리를 만들었습니다.

 

모든 단어의 사용 여부를 False로 초기화한 후, 사용한 단어는 True로 바꾸었고 방문할 단어를 큐에 넣을 때도 False인지 확인했습니다.

 

def solution2(begin, target, words):
    # 변환할 수 없는 단어인 경우
    if target not in words:
        return 0
    
    visited = {word:False for word in words}  # 방문 여부 표시, 달라진 부분
    # 큐에 현재 단어와 1글자 차이나는 단어 넣기
    queue = deque()
    queue.append([begin, 0])

    while queue:
        word, cnt = queue.popleft()
        visited[word] = True

        if word == target:
            return cnt

        # 변환할 수 있는 단어 모두 큐에 넣기
        for i in range(len(words)):
            if is_valid(words[i], word) and visited[words[i]] == False:  # 달라진 부분
                queue.append([words[i], cnt+1])
    
    return 0

테케 3 시간이 확연히 줄어든 것을 확인할 수 있습니다!!