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

TITLE

문제주소 :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

 

<풀이법>

▒ 한줄 개념: BFS ▒ 

예시 1로 생성해본 그래프

단어는 한번에 하나의 글자만 바꿀 수 있습니다. 이 말은 다시말하면, 한 글자만 바꾸면, 다른 단어로 이동하는 것이 됩니다. 예시 1에서, 각 단어들끼리 이동 가능한 것을 간선으로 만들어 그래프를 그리면 위와 같습니다.

 

1. hit에서 i를 o로 바꾸면 hot : hit -> hot 간선 연결
2. hot에서 h를 d 또는 l 로 바꾸면 dot 또는 lot : hot -> dot / lot 간선 연결
3. ....

 

위의 과정을 반복하면 하나의 그래프를 얻어낼 수 있고, 이 문제는 목적지까지의 최단경로를 구하는 것이 중요하므로 BFS를 이용해 이 그래프를 탐색하게 되면, 시작 단어부터 타겟 단어까지의 변환 횟수를 얻을 수 있습니다.

 

 

<코드(Python)>

def solution(begin, target, words):
    answer = 0
    word_length = len(begin)
    visited = {begin:False}
    queue = [begin]
    for i in range(len(words)):
        visited[words[i]] = False
    
    if target not in words:
        return 0
    else:
        queue_size = len(queue)
        while queue_size > 0:
            if target in queue:
                return answer
            for q in range(queue_size):
                cur = queue.pop(0)
                if not visited[cur]:
                    visited[cur] = True
                    for j in range(len(words)):
                        check = True
                        for i in range(word_length):
                            if cur[i] != words[j][i]:
                                if not check:
                                    check = True
                                    break
                                else:
                                    check = False
                        if not check:
                            queue.append(words[j])
            
            queue_size = len(queue)
            answer += 1
            
        return answer

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest

 

ㅁ