[programmers] 단어 변환 Python

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

프로그래머스

문제 설명

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

 

내 풀이_틀림 (채점결과 정확도 : 60/100)

minimum = 1e9
answer = 0
def solution(begin, target, words):
    global answer
    if target not in words:
        answer = 0
    
    def reversible(w1, w2):
        word1 = []
        for i in list(w1):
            word1.append(i)
        word2 = []
        for i in list(w2):
            word2.append(i)
        word1.sort()
        word2.sort()
        count = 0
        for i in word1:
            for j in word2:
                if i == j:
                    count += 1
        if count >= 2:
            return True
        else:
            return False
    
    graph = {} # key 변환할 문자 value 변환가능한 문자들
    for i in words:
        for j in words:
            if i == j:
                continue
            if reversible(i, j) == True: # i를 j로 바꿀 수 있으면
                if graph.get(i)==None:
                    graph[i] = [j]
                else:
                    graph[i].append(j)
    begin_reversible = []
    for i in words:
        if reversible(begin, i):
            begin_reversible.append(i)
    if begin not in words:
        graph[begin] = begin_reversible
        
    visited = [False]*len(words)
    
    def dfs(word1, count):
        global minimum
        global answer
        if word1 == target:
            minimum = min(minimum, count)
            answer = minimum
            return
        for idx, word in enumerate(words):
            for i in graph[word1]:
                if i == word and not visited[idx]:
                    visited[idx] = True
                    dfs(i, count + 1)
                    visited[idx] = False      
    
    dfs(begin, 0)
    return answer

바꿀 수 있는 것들 정보를 그래프로 만들어준다고 reversible 함수를 쓰고 .. 코드가 이렇게 길어졌다.

너무나 비효율적인 코드..

 

참고한 풀이

 

def solution(begin, target, words):
    n_words = len(words)
    visited = [False]*n_words
    answer = 1e9
    flag = 0
    def dfs(begin, target, nchange):
        nonlocal answer, flag
        if begin == target:
            flag = 1
            answer = min(answer, nchange)
            return
        for idx, word in enumerate(words):
            # 아직 방문하지 않았고
            if not visited[idx]:
                count = 0
                # 다른 글자가 하나 뿐이면
                for i in range(len(begin)):
                    if begin[i] != word[i]:
                        count += 1
                # 탐색
                if count == 1:
                    visited[idx] = True
                    dfs(word, target, nchange+1)
                    visited[idx] = False

    dfs(begin, target, 0)
    if flag == 1:
        return answer
    else:
        return 0

- 다른 글자가 한가지인 경우를 비교하는 구문 (처음에 매부 비효율적이게 작성)

- 첫 answer 값의 설정값 (처음엔 0으로)

- nonlocal 등 지역변수 전역변수에 대한 개념이 잡혀있지 않았음

*함수 안에서 전역변수 값을 변경하려면 global 키워드를 사용해야 한다.

*지역변수를 불러올 때는 nonlocal 키워드를 사용한다.

 

 

등등의 문제가 있었다.

코드 복습하자 !