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

문제 정보

제목 : 단어 변환

난이도 : Lv.3

사용 언어 : Python

문제 링크

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

프로그래머스

 

문제 설명

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

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

예를 들어 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 합니다.

 

입출력 예

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

 

입출력 예 설명

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

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

---

나의 풀이

BFS를 통해 문제를 해결했습니다. queue에 처음 단어를 넣고 queue에 요소가 있는 동안 반복하는 while 루프를 이용합니다. queue에서 단어를 하나 꺼내 만약 단어의 집합에 포함된 단어라면 curIDX에 words의 인덱스를 저장합니다. target과 같다면 현재 인덱스에 해당되는 visited를 return합니다. 중첩 for 루프를 이용해 알파벳을 하나씩 바꿔서 words에 있는지 확인 후, 방문하지 않았다면 curIDX에 따라 방문 리스트에 현재 단어의 방문 단계 +1을 저장하거나, 1을 저장합니다. 

반복이 수행되는동안 target를 찾지 못하고, 끝이 났다면 0을 return합니다.

코드

from collections import deque

def solution(begin, target, words):
    answer = BFS(begin, target,words)
    return answer

def BFS(begin, target, words) :
    visited = [0]*len(words) # 방문 여부 확인 리스트
    queue = deque([begin])
    curIDX = -1
    while(queue) :
        curWord = queue.popleft()
        if curWord  in words : # 단어의 집합에 포함된 단어라면 현재 단어 인덱스 저장함
            curIDX = words.index(curWord)
        
        if( curWord == target): # 현재 단어가 target와 일치하다면 visited에 현재 인덱스로 접근하여 return
            return visited[curIDX]
        
        # 단어 전부 순회함
        for i in range(len(curWord)):
            tmp = [c for c in curWord]
            for alphabet in range(ord("a"),ord("z")+1):
                tmp[i] = chr(alphabet)
                joinTmp = "".join(tmp)
                if(joinTmp in words ) : # 바꾼 알파벳이 단어의 집합에 있다면
                    nextIDX = words.index(joinTmp) # 다음 인덱스를 구함
                    if(visited[nextIDX] == 0) :
                        if curIDX != -1 : # 처음 주어진 단어가 아니라면
                            visited[nextIDX] = visited[curIDX] + 1 # 현재단어의 인덱스 + 1
                        else : # 처음 주어진 단어라면 1
                            visited[nextIDX] = 1 
                        queue.append(joinTmp)  
    return 0