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

단어변환 | Lv.3
https://school.programmers.co.kr/learn/courses/30/lessons/43163

 

 

작성 코드 (통과)

 

from collections import deque


def solution(begin, target, words):
    # target 값이 word에 없는 경우 바로 return (속도)
    if target not in words:
        return 0
    q = deque()
    q.append([begin])

    # bfs
    while q:
        v = q.popleft()

        # v[-1] 이 target인 경우 답!! return
        if v[-1] == target:
            return(len(v) - 1)
        
        for word in words:
            # v값 영향가지 않도록 값만 복사
            tmp = v[:]

            # 현재 방문할 word가 이미 방문한 tmp(v)에 있다면 pass
            if word in tmp:
                continue

            # 바로 이전의 값과 현재 삽입할 word가 한 글자만 다른지 확인
            if (sum([tmp[-1][i] != word[i] for i in range(len(begin))])) == 1:
                q.append(tmp + [word])
    return 0

 

• queue 에 방문 기록들 다 저장함

 

 

이상 코드

 

from collections import deque

# 값이 하나만 다른 지 판별해주는 함수
def get_adjacent(current, words):
    for word in words:
        count = 0

        # zip 을 통해 (current[i] word[i]) 를 가져오는 효과
        for c, w in zip(current, word):
            if c != w:
                count += 1

        # 하나만 다른 word들을 generator return
        if count == 1:
            yield word


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

    while queue:
        current = queue.popleft()

        # get_adjcent 함수를 통해 current 값과 words 를 넘김, 하나만 다른 word를 받아옴
        for next_word in get_adjacent(current, words):
            # 만약 방문하지 않았다면!
            if next_word not in dist:
                # 이전까지 걸린 dist에 +1 해서 저장함
                dist[next_word] = dist[current] + 1
                # 경로가 아닌 당장 방문할 word만 저장
                queue.append(next_word)

    # get 함수를 통해 dist의 target 값을 return 없다면 0 return
    return dist.get(target, 0)

 

• yield를 사용한 유용한 풀이 (yield 설명 : https://www.daleseo.com/python-yield/, https://data-newbie.tistory.com/774)
  • yield가 호출되면 임시적으로 return이 호출되며, 한번 더 실행되면 실행되었던 이전 yield의 다음 코드가 실행
  • get_adjacent에서 처음으로 yield return 된 후에도 이어서 돈다

 

• dist.get() 첫번째 인자 -> 찾는 값!
  • 2번째 인자 생략 가능, 찾는 값이 없다면 생략 시 None return, 기입 시 해당 값 return 

 

• dist 에는 해당 원소까지 가는 최단 거리 값이 저장됨 

{'hit': 0, 'hot': 1, 'dot': 2, 'lot': 2, 'dog': 3, 'log': 3, 'cog': 4}