Programmers : 단어변환

문제 설명

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

예를 들어 begin이 “hit”, target가 “cog”, words가 [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]라면 “hit” -> “hot” -> “dot” -> “dog” -> “cog”와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한 사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

입출력 예에 대한 설명

예제 #1 문제에 나온 예와 같습니다.

예제 #2 target인 “cog”는 words 안에 없기 때문에 변환할 수 없습니다.

풀이

너비우선탐색에 대해서 알아보겠습니다.

• 그래프에서 가까운 노드부터 탐색하는 알고리즘으로 큐 자료구조를 이용합니다.
• 알고리즘의 진행 순서는 다음과 같습니다.
  • 1) 탐색 시작 노드를 큐에 삽입하고 방문처리를 한다.
  • 2) 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드들을 큐에 삽입하고 방문처리
  • 3) 2번의 과정을 더 이상 반복할 수 없을 때까지 반복
• 너비 우선 탐색은 가까운 노드부터 탐색하므로, 모든 간선의 비용이 1인 그래프에서 BFS를 사용하면 최단 거리를 계산할 수 있습니다.

너비우선탬색(bfs)를 이용해 target 단어에 도달하는 최단 시간을 구해보겠습니다.

1) 큐에 시작 위치 및 소요시간(=0) 삽입합니다.

2) 큐의 맨 앞에서 하나를 추출하고 그 다음단어 후보를 다시 큐에 넣어줍니다.
    - 큐에 넣을때 소요시간을 1씩 더해줍니다.
    - 방문했던 단어였다면 제외합니다.

3) 2)을 계속 반복하다가 target단어가 되면 return합니다.

4) 최종 소요시간을 출력합니다.

단어 후보를 출력하는 함수를 따로 생성합니다.(possible_words) 일일이 words의 단어들과 비교하여 다른 스펠이 하나만 있는 word만 출력하도록 합니다.

ex) hit -> [‘hot’]

from collections import deque

def possible_words(begin, words):
    words_list = []
    for word in words:
        diff = 0
        for i in range(len(begin)):
            if begin[i] != word[i]:
                diff += 1
        if diff == 1:
            words_list.append(word)

    return words_list

def solution(begin, target, words ):
    visited = []
    queue = deque()
    queue.append((begin,0))
    visited.append(begin)
    while queue:
        word, count = queue.popleft()
        if word == target:
            return count
        for next_word in possible_words(word, words):
            if next_word not in visited:
                queue.append((next_word, count+1))
                visited.append(next_word)
    return 0