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

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

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

나의 풀이

from collections import deque
def check_one_word(word,begin):
    counting = 0
    for w,b in zip(word,begin):
        if w != b:
            counting +=1
    return True if counting ==1 else False

def solution(begin,target,words):
    if target not in words:
        return 0
    queue = deque()
    queue.append([begin,[]])
    
    while queue:
        n, l = queue.popleft()
        
        for word in words:
            if word not in l and check_one_word(word,n):
                if word == target:
                    return len(l)+1
                else:
                    temp = l[:]
                    temp.append(word)
                    queue.append([word,temp])

해결 아이디어 :

1. 최소 과정이라 했으니 bfs가 생각이 났다

2. 한 단어씩 변환해야 한다고 하니 한글자씩 변환됐는지 확인하는 함수를 선언했다.

 

위의 두 방식으로 푸니 하나의 테스트 케이스에서 시간 초과 에러가 발생했다.

 

생각해보니 내 코드는 위의 두 조건만 만족했을 때, queue에 계속 넣기만 했기 때문에

테스트 케이스만 잘 만들면 똑같은 word 집합을 무한루프를 돌 수 있다는 것을 알게 되었다.

 

그래서 현재까지 방문했던 단어는 제외하고 검사시키는 코드를 작성했다.

 

다른 풀이

from collections import deque


def get_adjacent(current, words):
    for word in words:
        if len(current) != len(word):
            continue

        count = 0
        for c, w in zip(current, word):
            if c != w:
                count += 1

        if count == 1:
            yield word


def solution(begin, target, words):
    dist = {begin: 0}
    queue = deque([begin])

    while queue:
        current = queue.popleft()

        for next_word in get_adjacent(current, words):
            if next_word not in dist:
                dist[next_word] = dist[current] + 1
                queue.append(next_word)

    return dist.get(target, 0)

위의 코드는 제너레이터와 dict를 활용한 깔끔한 코드라 가져왔다.

애초에 words 전체를 함수에 넣고, 이들 개별 검사하여 제너레이터에 넣어 바로 for loop를 돌 수 있게 만들었다.

또한 dict를 활용해 이미 있는 단어였는지 + dict.get 메소드로 없을 때 0을 출력하는 좋은 코드다.