# 단어변환(BFS) - 프로그래머스

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

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

입출력 예

begin = "hit"
target = "cog"
words= ["hot", "dot", "dog", "lot", "log", "cog"]
return 4

접근 방법

• 가장 짧은 변환 과정, 즉 최소값을 찾는 문제이므로 BFS 가 적절하다.
• BFS(Breadth-First Search) : Queue 구조 사용. 발견 phase와 방문 phase 가 따로 있는 점에 유의하자. 큐 구조와 while문 사용
  1. 노드 찾기 : 후보군 중 조건에 맞는 word를 큐에 저장, 여기서 같은 depth를 갖는 노드들이 순차적으로 저장됨.(아직 visit하지 않은 상태)
  2. 큐 앞순서부터 방문하면서, 다음 depth 후보군들을 큐에 저장.

코드 (다른 분들의 풀이를 참고하였음)

• BFS 방법1

    from collections import deque

    def available(w1, w2):
        wrong = 0
        for i in range(len(w1)):
            if w1[i] != w2[i]:
                wrong += 1
            if wrong > 1:
                return False
        return True

    def bfs(word, target, words):
        queue = deque()
        queue.append([word, 0, []])
        while queue:
            cur = queue.popleft()
            depth = cur[1] 
            path = cur[2]

        	if cur[0] == target:
            	return depth

        	for w in words:	
            	if available(cur[0], w):
                	if w not in path: 
                    	queue.append([w, depth + 1, path + [w]])
    	return 0


    def solution(begin, target, words):
    
        if target not in words:
            return 0
        return bfs(begin, target, words)