[Python] Level 3. 단어 변환

프로그래머스

 

문제 설명

begin 단어와 target 단어가 주어질 때,

words에 있는 단어들을 조합해 begin에서 target으로 변환할 수 있는 최소 단계를 구한다.

✅ 단, 단어 사이에 한 개의 알파벳만 변환할 수 있다.

 

 

문제 풀이

(1) 사용한 알고리즘

BFS

 

(2) 시간복잡도

O(n2)

 

(3) 설명

1. 변환할 수 있는 다음 단어 구하기

def getNextWord(curr, words):
    for word in words:
        cnt = 0
        for c, w in zip(curr, word):
            if c != w:
                cnt += 1
                
        if cnt == 1:
            yield word

getNextWord는 파라미터로 주어진 curr 단어를 변환할 수 있는 다음 단어들을 찾는 함수이다.

 

words를 완전 탐색하면서 하나의 알파벳만 변하는 word들을 찾아 리턴하는데,

이 때 yield 키워드로 리턴하면 굳이 모든 word들을 넣은 리스트로 반환하지 않아도 되므로

추가적인 메모리 낭비 없이 쉽게 리턴할 수 있다는 장점이 있다.

 

 

2. BFS를 위한 Queue & word별 단계 수를 담는 딕셔너리 초기화

levels = {begin: 0}
q = [begin]

• levels = word별로 해당 word로 변환되기까지 걸리는 최소 단계를 담는 딕셔너리 (BFS에 주로 쓰이는 visited 배열과 비슷한 용도)
• q = BFS를 위해 현재 탐색할 word를 담는 큐

✅ begin 단어부터 시작하므로 큐에 begin을 담아서 BFS 탐색을 시작한다.

✅ 큐 자료구조로 파이썬의 deque를 쓰는데, 이번 문제는 큐의 길이 자체가 50이하이기 때문에 간편하게 리스트로 구현했다.

 

 

3. BFS 구현하기

def solution(begin, target, words):
    levels = {begin: 0}
    q = [begin]
    
    while q:
        curr = q.pop(0)
        for nextWord in getNextWord(curr, words):
            if nextWord not in levels:
                levels[nextWord] = levels[curr] + 1
                q.append(nextWord)
                
        if target in levels:
            break
                
    if target not in levels:
        return 0
    return levels[target]

큐에 들어 있는 word를 꺼내서, 해당 word를 변환할 수 있는 다음 단어를 getNextWord를 통해 구한다.

이 때 nextWord가 levels에 없는 경우, 즉 처음 방문한 word이므로 levels에 업데이트한다. 

✅ levels에 이미 nextWord가 있다면, 이미 앞서 nextWord의 최소 level을 구했기 때문에 업데이트할 필요가 없다.

 

그리고 그 nextWord가 우리가 찾는 target이라면, 더 탐색할 필요가 없으므로 BFS를 종료한다.

 

최종적으로 levels에 target이 담겨있다면 해당 값을, 아니라면 0을 return한다.

 

 

4. (효율을 위해) 예외 처리

if target not in words:
    return 0

BFS를 실행하기 이전에 words에 target이 없다면 바로 0을 리턴하는 예외 처리를 한다.

 

 

(4) 풀이 코드

def getNextWord(curr, words):
    for word in words:
        cnt = 0
        for c, w in zip(curr, word):
            if c != w:
                cnt += 1
                
        if cnt == 1:
            yield word

            
def solution(begin, target, words):
    if target not in words:
        return 0
    
    levels = {begin: 0}
    q = [begin]
    
    while q:
        curr = q.pop(0)
        for nextWord in getNextWord(curr, words):
            if nextWord not in levels:
                levels[nextWord] = levels[curr] + 1
                q.append(nextWord)
                
        if target in levels:
            break
                
    if target not in levels:
        return 0
    return levels[target]