[알고리즘] 단어 변환 (프로그래머스 DFS/BFS Level 3)

문제 설명

두 개의 단어 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

 

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

 

 

---

 

문제 풀이 접근 방법

나는 DFS 깊이 우선 탐색을 이용하여 위 문제를 해결하였다. words 리스트들 중 현재 최적이라고 판단하는 요소를 선택해 나가면서, 최소의 깊이를 구하는 문제이기 때문에 각각 최솟값으로 갱신하면서 가지치기를 적절하게 해나가며 경우의 수를 줄여 나가는 것이 핵심이다.

 

문제 풀이

초깃값 설정

    global answer
    answer = 50 # 마지막에 target값을 찾는 경우
    check = [0] * len(words) # 방문 여부

 

초기의 answer은 50으로 설정해주었다. begin에서 target으로 변환할 때, words의 단어를 모두 탐색하다가 마지막에 target 값이 나오는 경우가 최악의 경우이고, 문제의 조건에서 words의 최대값은 50으로 주어졌기에 초기의 answer에 최악이 발생할 수 있는 상황에서의 최대값인 50을 넣어주었다.

check 는 words의 각 단어를 현재 선정(방문)했는지 아닌지 여부를 저장하는 리스트이다.

 

target이 words 리스트에 포함되어 있어야 해결이 가능한 문제이므로, 리스트 전체 탐색하여 없는 경우는 곧바로 0을 리턴하도록 구현했다.

 

---

재귀의 구현

DFS 재귀 함수의 파라미터들은 다음과 같이 설정해주었다.

def DFS(L, check, cur, target, words):

 

• L: 깊이 
• check: 선정 여부 저장한 배열
• cur: 이전 level로부터 선정된 현재 단어 (초기: begin)
• target: 결과적으로 도달하고자 하는 단어
• words: 단어들 저장되어 있는 초기 배열

 

    global answer
    # 가지치기
    if L > answer:
        return
    if cur == target:
        if L < answer:
            answer = L # 더 작은 값으로 설정
        return

 

우리가 begin 단어부터 target 단어까지 가장 짧은 변환 과정을 거치는 것이 목표이기 때문에, 깊이 L 이 최소화되는 것이 목표이다. global 전역 변수로 설정한 answer에 L이 작은 것으로 갱신될 때마다 해당 값을 넣어주며, 최종 가장 작은 값의 answer을 구하고자 하는 것이다.

 

따라서 재귀 DFS 함수가 호출될 때마다 현재 단어 cur을 확인하여 해당 값이 target과 같다면, 현재의 Level (깊이) 가 현재까지의 재귀 호출 중 가장 작았던 answer 값보다 더 작다면 answer을 해당 Level로 갱신해준다.  (if cur == target)

이때, 현재 깊이가 지금까지 호출되었던 재귀 중 가장 작은 answer 의 값보다 크면 더이상 해당 가지는 볼 필요도 없으므로 가지치기를 해주는 것이 시간 복잡도를 줄이는 방법이다. (if L > answer)

 

 

        for i in range(len(words)):
            if check[i] == 0:      
                diff = 0
                for j in range(len(target)):
                    if cur[j] != words[i][j]:
                        diff += 1
                        if diff > 1:
                            break
    
                if diff == 1:
                    check[i] = 1
                    DFS(L + 1, check, words[i], target, words)
                    check[i] = 0  # backtracking

 

 

위의 조건 중 해당되는 것이 없다면, words 리스트들 중 아직 선정하지 않은 단어들에 대해서 문자 하나만 차이나는 문자인지 확인하는 과정을 거친다. 

0의 default 값을 갖는 변수 diff을 이용하여, 문자가 1개만 다른 단어를 다음 방문할 단어로 선정하여 다음 재귀로 선정된 해당 단어를 파라미터 cur로 설정해준다.

 

 

---

 

 

전체 소스코드 

 

def DFS(L, check, cur, target, words):
    global answer
    # 가지치기
    if L > answer:
        return
    if cur == target:
        if L < answer:
            answer = L # 더 작은 값으로 설정
        return
    
    else:
        for i in range(len(words)):
            if check[i] == 0:      
                diff = 0
                for j in range(len(target)):
                    if cur[j] != words[i][j]:
                        diff += 1
                        if diff > 1:
                            break
    
                if diff == 1:
                    check[i] = 1
                    DFS(L + 1, check, words[i], target, words)
                    check[i] = 0  # backtracking

def solution(begin, target, words):
    global answer
    answer = 50 # 마지막에 target값을 찾는 경우
    check = [0] * len(words) # 방문 여부
    
    if target not in words:
        return 0
    else:
        DFS(0, check, begin, target, words)  # level, check, cur, target, words
    return answer

if __name__=='__main__':
    print(solution("hit","cog",["hot", "dot", "dog", "lot", "log", "cog"])==4)
    print(solution("hit","cog",["hot", "dot", "dog", "lot", "log"])==0)
    print(solution("abc", "aaa", ["abb", "abd", "bbc", "acc", "aac", "aba", "aaa", "ccc"])==2)