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

728x90

문제설명

두 개의 단어 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를 통해 쉽게 해결할 수 있다.

마치 다익스트라 알고리즘처럼 구상하면 된다.

이 문제를 진행하다가 하나 이상한 점을 느낄 수 있었다.

문제를 처음 접근했을 때 인접리스트를 만들어서 출력해보았는데,

그래프처럼 보이는 이 문제는 사실 트리 탐색 문제이다.

words를 연결해보면, 아마 단방향 그래프의 인접리스트 형태를 갖고 있을 것이다.

위 예시의 경우 인접리스트는 아래와 같은 형태로 작성된다.

[[1], [2, 4], [3, 4], [5, 6], [5], [6], None]

이를 그림으로 나타내면 아래와 같다.

물론 양방향으로 연결하면 그래프 형태를 갖는다.

하지만, 우리는 words로 가는 경우를 정리하고 거리를 계산하면 된다.

따라서 0부터 차례로 큐에 넣으면서 트리를 순회하면 된다.

순회하면서 거리값을 계산해주면 된다.

이동가능여부 (연결되어 있는지 여부)는 간단하다.

조건에서 글자의 길이는 같다고 언급되어 있기 때문에, 이를 고려해서 모든 자릿수를 비교해주면 된다.

비교하여 하나의 글자만 틀린 경우를 큐에 넣어준다.

(글자 개수나, 길이 자체가 짧기에 큰 문제가 되지 않는다.)

더불어 트리 형태에서 최단거리 찾기 이므로,

처음 target을 발견하는 경우가 bfs에서의 최단거리라고 정의할 수 있다.

따라서 target 단어가 나오는 경우 바로 return해주면 쉽게 문제를 해결할 수 있다.

정답코드

from collections import deque

def compare_str(begin, target):
    cnt = 0
    for b, t in zip(begin, target):
        if b != t:
            cnt += 1
    return True if cnt == 1 else False
    
def solution(begin, target, words):
    if target not in words:
        return 0
    
    queue = deque()
    queue.append((begin, 0))
    
    while queue:
        cur, cost = queue.popleft()
        if cur == target:
            return cost
        
        for word in words:
            if compare_str(cur, word):
                queue.append((word, cost + 1))