Programmers / 단어 변환 / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 단어 변환 (3단계, DFS)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/43163

프로그래머스

문제 설명

두 개의 단어 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 합니다.

입출력 예begintargetwordsreturn

"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

입출력 예 설명

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

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

---

나의 풀이 (테스트 케이스 통과, 첫 풀이 20점)

너무 너프하게 구현해서 그런가 코드도 길고 경우의 수도 너무 길어졌다 ㅠㅠ

일단 정답은 찾아지긴 함 ㅎ.. 경우가 최적의 경우가 아니라서 그렇지..

import re
def solution(begin, target, words):
    answer = 1
    # 한 단계에 한 개의 알파벳을 바꿈
    # 한 개의 알파벳을 바꿀 수 있는 단어는 제시해줌
    # 거기서 골라라
    
    if target not in words:
        return 0
    if target == words:
        return 1
    
    words_dict = {i:[] for i in words}
    words_dict[begin] = []
    
    for word in words_dict:
        words_dict[word].extend(Check_words(word,words)) # 단어에 대한 딕셔너리 생성
        
    reuslt_list = DFS(words_dict,begin,target)
    print(reuslt_list)
    if reuslt_list == []:
        return 0
    else:
        return len(reuslt_list) -2
    
def DFS(words_dict,start_word,target):
    word_set = list()
    visited = list()
    stack = list()
    stack.append(start_word)
    
    while stack:
        node = stack.pop()
        word_set.append(node)
        if node == target:
            print("TARGET")
            break
        
        if node not in visited: # 방문한 노드가 아니라면
            visited.append(node)
            tmp_list = words_dict[node]
            for tmp in tmp_list:
                if (tmp in visited) or (tmp in word_set) or (tmp in stack):
                    tmp_list.pop(tmp_list.index(tmp))
            stack.extend(tmp_list)
    if word_set[-1] != target:
        return []
    return word_set

def Check_words(checkword,words):
    result = []
    for word in words:
        checkwords = []
        for i in range(len(checkword)):
            tmp = list(checkword)
            tmp[i] = '.'
            checkwords.append("".join(tmp))
        for check in checkwords:
            if re.match(check,word):
                if checkword != word:
                    result.append(word)
    return list(set(result))

출력결과

 

 

* dict.fromkeys(seq, value)

• 딕셔너리를 생성할 때 편리하게 사용할 수 있는 메소드. seq 옵션 값에 문자열을 입력할 수도 있다.
• seq: 생성하려는 dictionary의 키(key)의 목록
• value: 생성하려는 dictionary의 값(value)

사용 예시

seq = ('name', 'age', 'sex')

dict_1 = dict.fromkeys(seq)
print(dict_1)

dict_2 = dict.fromkeys(seq, 10)
print(dict_2)

## result ##
{'age':None, 'name':None, 'sex':None}
{'age':10, 'name':10, 'sex':10}

출처

 

해당 방법을 이용해서 코드를 줄일 수 있다!

 

나의 풀이 ( DFS 수정, solution 함수 수정 )

import re
res = float('inf')
def solution(begin, target, words):
    answer = 1
    visited = []
    global res
    # 한 단계에 한 개의 알파벳을 바꿈
    # 한 개의 알파벳을 바꿀 수 있는 단어는 제시해줌
    # 거기서 골라라
    
    if target not in words:
        return 0
    if target == words:
        return 1
    
    words_dict = dict.fromkeys(words,[])
    words_dict[begin] = []
    for word in words_dict:
        words_dict[word] = Check_words(word,words) # 단어에 대한 딕셔너리 생성
    DFS(begin,words_dict,begin,target,0,visited)
    
    return res
    
def DFS(next_word,words_dict,begin,target,L,visited):
    global res
    extend_list = words_dict[next_word]
    if next_word not in visited:
        visited.append(next_word)
    else:
        return

    if L >= res:        
        return
    
    if visited[-1] == target:
        if L < res:
            res = L
    else:
        for i in range(len(extend_list)):
            DFS(extend_list[i],words_dict,begin,target,L+1,visited)
    

def Check_words(checkword,words):
    result = []
    for word in words:
        checkwords = []
        for i in range(len(checkword)):
            tmp = list(checkword)
            tmp[i] = '.'
            checkwords.append("".join(tmp))
        for check in checkwords:
            if re.match(check,word):
                if checkword != word:
                    result.append(word)
    
    return sorted(list(set(result)))

 

함수를 하나하나 뜯어가면서 처음엔 DFS 부분이 가장 문제인 줄 알았는데, 처음 짠 코드는 생각보다 문제점이 여러개 있었다..

1. sort를 안해서 각 딕셔너리가 갖고있는 value의 순서가 set함수 때문에 매번 랜덤으로 배치되어 DFS가 실행됨

2. check_words 함수를 사용하고 각 딕셔너리 키에 대응하는 값에 extend를 해줘서 값이 중복이됨 

해당 코드로 실행 결과

 

 

따라서 확장이 아닌 할당으로 해줌

해당 코드로 실행 결과

 

3. 이전 코드는 최적의 경로를 구했을 때의 가지수를 저장하지 않음 (매번 최소 비용의 값이 업데이트 되지않음)

---

※ 알아야 할 것

- DFS 함수를 사용해서 컴퓨터 내의 프로세스 실행과정을 하나의 스택이라고 생각하자