[프로그래머스] 단어 변환 (lv.3)

문제

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

프로그래머스

 

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

한 번에 한 개의 알파벳만 바꿀 수 있습니다.
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 함수를 작성해주세요.

---

풀이

from collections import deque

def solution(begin, target, words):
    if target not in words:  # 애초에 words리스트에 target값이 없다면 return 0
        return 0

    answer = 0

    q = deque()
    q.append([begin, 0])  # 시작단어와 깊이를 넣어준다.

    while q:
        x, cnt = q.popleft()  # 단어, 이동한 횟수

        if x == target:
            return cnt

        # 단어를 모두 체크하면서, 해당 단어가 변경될 수 있는지 체크
        for i in range(len(words)):
            diff = 0  # 다른 글자의 갯수
            word = words[i]

            for j in range(len(x)):  # 단어의 길이만큼 반복
                if x[j] != word[j]:  # 단어에 알파벳 한개씩 체크하기
                    diff += 1
            if diff == 1:
                q.append([word, cnt + 1])

    return answer

 

 

---

설명

- 최소 단계를 구하라고 해서 완전 탐색 or bfs/dfs 로 생각했다.

처음에 완전 탐색 문제로 해결하려고 했으나 실패했다...

 

대부분의 bfs 문제 에서는 큐에 x,y 좌표를 넣고 상하좌우 방향으로 이동할 x,y 좌표에 따라 문제를 풀었었다.

이 문제가 처음부터 풀이되지 않았던 이유는, 큐에 넣을 때 [시작단어, 깊이] 로 넣는다는 것이였다.

그리고 popleft() 하면서 단어가 1글자만 다를때 큐에 넣어서 넓이 우선 탐색을 실시했다.

 

2) 해당 단어가 words 에 존재하는 단어들 중 1개의 알파벳값만 다르다면 큐에 넣어주고 반복한다.
3) 큐에서 단어를 pop 했을 때, 만약 target값을 찾으면 지금까지 세어준 단계를 반환한다.