[프로그래머스] 단어 변환 - Python3

문제

begin 단어에서 words의 단어들을 거쳐 target이 되기 위한 최소 변환 횟수를 구하는 문제. 한 변환 당 한글자만 바꿀 수 있음.

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

프로그래머스

• 알고리즘 분류 - 깊이/너비 우선 탐색(DFS, BFS)
• 난이도 - Level 3

---

접근 방법

1. BFS

최소거리니까 BFS가 유리할까 싶어 먼저 시도해봤다.

words 내에 한 글자를 제외하고 스펠링이 같은 단어가 있으면, 큐에 (단어, 레벨)을 넣고, 단어가 target이 되었을 때의 최소 레벨을 리턴한다. target이 되지 못하면 0을 반환한다.

 

2. DFS

스택을 사용해 pop한 단어가 target이 될 때까지 pop과 push를 반복하고, target이 되었다면 반복횟수를 리턴하도록 풀었다.

 

이게 되네 싶었던 풀이였다. 왜나면 DFS로는 구한 해가 최적의 해임을 보장할 수 없기 때문이다.

위 BFS풀이처럼 최솟값을 구하면 최적의 해가 나올 수도 있겠지만, 나는 단순히 target에 도달했을 때의 횟수를 리턴하도록 했는데 풀렸다.

테스트케이스가 깐깐하지 않았던 것 같다.

 

그래서 반례를 생각해봤는데, 역시나 최적의 해가 나오지 않았다.

begin = "hit"
target = "cog"
words = ["hot", "dot", "dog", "dat", "lot", "log", "cog", "hat", "lat"]

로 해서 실행해보면 4가 나와야 하는데, 5가 나온다.

 

백트래킹을 쓰면 DFS로도 최적의 해를 구할 수 있을 것 같은데, 재귀 없이 스택만으로도 가능할지는 모르겠다. 나중에 해보는 걸로....

---

답안 코드

1. BFS

from collections import deque

def solution(begin, target, words):
    mini = 5000000
    q = deque()
    q.append((begin, 0))
    visited = []
    while q:
        word, lv = q.popleft()
        
  		# 단어 완성 시 최솟값 갱신
        if word == target:
            mini = min(lv, mini)
        
        # 한 글자 빼고 스펠링 같은 단어들 인큐
        for w in words:
            if w != word and w not in visited:
                for i in range(len(w)):
                    if w[:i] == word[:i] and w[i+1:] == word[i+1:]:
                        q.append((w, lv+1))
                        visited.append(w)
                        break
    
    if mini == 5000000:
        return 0
    
    return mini

 

2. DFS

from collections import deque

def solution(begin, target, words):
    answer = 0
    word = begin
    q = deque()
    
    visited = []
    while word != target:
    	# 한 글자 빼고 스펠링 같은 단어들 push
        for w in words:
            if w != word and w not in visited:
                for i in range(len(w)):
                    if w[:i] == word[:i] and w[i+1:] == word[i+1:]:
                        q.append(w)
                        visited.append(w)
                        break
        if not q:
            return 0
        answer += 1
        word = q.pop()
    
    return answer