[Lv3] 단어 변환 - python

프로그래머스

문제 설명

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

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

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

 

제한 사항

1. 각 단어는 알파벳 소문자로만 이루어져 있습니다.

2. 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.

3. words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.

4. begin과 target은 같지 않습니다.

5. 변환할 수 없는 경우에는 0을 return 합니다.

 

풀이

너비우선탐색(BFS)를 이용하면 쉽게 풀 수 있는 문제입니다. 🤗

1. 모든 단어별 변환 가능 여부를 간선으로 표시하기

먼저 문제를 그래프 탐색으로 바꾸기 위해 각 단어별로 변환이 가능할 경우 간선을 연결해주도록 하겠습니다.

# words에는 begin이 포함되어 있지 않으므로, begin을 리스트 앞에 추가해줍니다.
words = [begin] + words
# 각 단어별 연결관계를 나타낼 dictionary(?)
maps = {}

for i in range(len(words)-1):
	for j in range(i+1, len(words)):
    	if check(words[i], words[j]): # 변환 가능
        	if i in maps: maps[i].append(j)
            else: maps[i] = [j]
            if j in maps: maps[j].append(i)
            else: maps[j] = [i]

여기서 사용된 check 메서드는 문제에 주어진 조건을 충족하여 변환이 가능하다면 True를, 불가능하다면 False를 반환하는 메서드입니다.

단어의 길이와 개수가 많지 않으므로, 하나씩 비교해서 알파벳이 하나만 다를 경우에 True를 반환해주도록 하였습니다.

def check(a, b):
    diff = 0
    for i in range(len(a)):
        if a[i] != b[i]: diff+=1
    return diff <= 1

 이렇게 만들어진 그래프에서 너비 우선 탐색을 통해 begin에서부터 target까지의 최소 거리를 구하면 됩니다. 😌👍🏻

begin은 0번 정점이므로, 0번부터 시작하는 너비우선 탐색을 구현해보겠습니다!

 

코드

def solution(begin, target, words):
    answer = 0
    
    # target이 words에 포함되어 있지 않은 경우
    if target not in words: return 0
    target = words.index(target) + 1
    
    # 각 단어별 변환 가능 여부로 간선 연결하기
    words = [begin] + words
    maps = {}
    
    for i in range(len(words)-1):
        for j in range(i+1, len(words)):
            if check(words[i], words[j]): # 변환 가능
                if i in maps: maps[i].append(j)
                else: maps[i] = [j]
                if j in maps: maps[j].append(i)
                else: maps[j] = [i]
    
    queue = []
    visited = [False] * len(words)
    queue.append((0,0))
    visited[0] = True
    
    while queue:
        start, cost = queue.pop(0)
        if start == target:
            return cost
        
        for end in maps[start]:
            if not visited[end]:
                visited[end] = True
                queue.append((end, cost+1))
                
    return 0

def check(a, b):
    diff = 0
    for i in range(len(a)):
        if a[i] != b[i]: diff+=1
    return diff <= 1