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

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

프로그래머스

문제 개요

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

input
- begin 단어
- target 단어
- words 단어의 집합

*각 단어는 알파벳 소문자로만 이루어져 있습니다.
*각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
*words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
*begin과 target은 같지 않습니다.

output
최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지의 값.
*변환할 수 없는 경우에는 0를 return

ex)
input: "hit" / "cog" / ["hot", "dot", "dog", "lot", "log", "cog"]
output: 4
"iii", "jjj", ["iij", "jjj", "iji", "jij"]

 

 

BFS + Depth

from collections import deque

def qualify(now, word):
    no = list(now)[:]
    wor = list(word)[:]
    for x in now:
        if x in word:
            if (x in no) and (x in wor):
                no.remove(x)
                wor.remove(x)
    if (len(no)==1) and (len(wor)==1):
        return True
    else:
        return False

def solution(begin, target, words):
    words.append(begin)
    queue = deque()
    queue.append(begin)
    visited = [0]*len(words)

    for x in words:
        if x == begin:
            visited[words.index(x)] = 1
    if target not in words:
        return 0
    while queue:
        now = queue.popleft()
        for idx, word in enumerate(words):
            if qualify(now, word) and (visited[idx]==0):
                queue.append(word)
                visited[idx] = visited[words.index(now)] + 1
            answer = visited[words.index(target)]
            if answer != 0:
                return answer-1

    if answer == 0:
        return 0

• 게임맵 최단거리 로직과 비슷했다
• BFS + Depth
• 가능한 다음 단어 찾는 qualify 함수 추가
• begin의 단어가 words 리스트에 포함될 경우에 대한 별도 처리 필요!!! (처음 에러 이유)
• 하지만 위 코드 역시 더 간결하게 정리될 필요성이 있다. 다시 복습해야지..