프로그래머스 단어 변환 -깊이/너비 우선 탐색(DFS/BFS)

• 처음에 테스트 케이스만 보고 나이브하게 생각했다.
• 어차피 최소 단계는 (글자수 + 1) 아니냐... len(begin)+1 리턴하면 되지?

• 그 결과는 당연히 실패지 ㅋㅋㅋ
• 엄청 꼬아놓은 것이 분명했다.
• hit -> hot -> hom -> mom -> mow -> cow -> cog 이런 식...

• 그리고 처음에 변환할 수 있는 단어도 여러 개일 가능성이 있다.
• hit -> hot, hin, cit 이렇게 다 바꿀 수도 있을거고...
• 결국 출발지는 여러 개고 도착지는 하나인 샘.
• 그리고 그 중에 가장 짧은 경로를 고르는 문제.

문제 설명

두 개의 단어 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나 BFS 쓰는 문제라고 했으니... 다시 제대로 생각해보기...
• 귀찮으니 그냥 딕셔너리에 넣고 for 문 돌려... 왜 실패나지?

def solution(begin, target, words):
    answer = 0

    if target not in words:
        return answer
    
    words_bridge = {}
    words_bridge[begin] = 0
    for word in words: words_bridge[word] = 999
    
    for depth in range(len(words)):
        print(words_bridge)
        for key, value in words_bridge.items():
            if value == depth:
                for word in words:
                    if len(set(list(word)) & set(list(key))) >= 2:
                        if words_bridge[word] > depth:
                            words_bridge[word] = depth + 1
                            if word == target:
                                return words_bridge[target]

    print(words_bridge)
    return words_bridge[target]
    
테스트 1
입력값 〉	"hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]
기댓값 〉	4
실행 결과 〉	테스트를 통과하였습니다.
출력 〉	
{'hit': 0, 'hot': 999, 'dot': 999, 'dog': 999, 'lot': 999, 'log': 999, 'cog': 999}
{'hit': 0, 'hot': 1, 'dot': 999, 'dog': 999, 'lot': 999, 'log': 999, 'cog': 999}
{'hit': 0, 'hot': 1, 'dot': 2, 'dog': 999, 'lot': 2, 'log': 999, 'cog': 999}
{'hit': 0, 'hot': 1, 'dot': 2, 'dog': 3, 'lot': 2, 'log': 3, 'cog': 999}

테스트 2
입력값 〉	"hit", "cog", ["hot", "dot", "dog", "lot", "log"]
기댓값 〉	0
실행 결과 〉	테스트를 통과하였습니다.

정확성  테스트
테스트 1 〉	실패 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.26ms, 10.3MB)
테스트 3 〉	실패 (0.02ms, 10.2MB)
테스트 4 〉	통과 (0.03ms, 10.2MB)
테스트 5 〉	통과 (0.00ms, 10.2MB)

• 한참 생각해보니
  • 아... 필요한 글자가 있는게 아니라... 글자 순서도 동일해야 하는구나!
    • 쉽게 가려고 했던 이 코드가 발목을 잡았네. 괜히 시간 낭비 했다. 
    • if len(set(list(word)) & set(list(key))) >= 2:

def solution(begin, target, words):
    answer = 0

    if target not in words:
        return answer
    
    words_bridge = {}
    for word in words: words_bridge[word] = 999
    words_bridge[begin] = 0
    
    i_will_leave_here = False
    for depth in range(len(words)):
        if i_will_leave_here == True:
            break
        for key, value in words_bridge.items():
            if value == depth:
                for word in words:
                    diffrent_character = 0
                    for i in range(len(word)):
                        if list(word)[i] != list(key)[i]:
                            diffrent_character += 1
                    if diffrent_character == 1:
                        if word == target:
                            i_will_leave_here = True
                        if words_bridge[word] > depth + 1:
                            words_bridge[word] = depth + 1

    #print(words_bridge)
    return words_bridge[target]

• 그거 말고도 틀린 부분 있었는데 ㅎㅎㅎ

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.16ms, 10.1MB)
테스트 3 〉	통과 (1.64ms, 10.2MB)
테스트 4 〉	통과 (0.02ms, 10.2MB)
테스트 5 〉	통과 (0.00ms, 10MB)

• 고수의 풀이

from collections import deque

def get_adjacent(current, words):
    for word in words:
        if len(current) != len(word):
            continue
        count = 0
        for c, w in zip(current, word):
            if c != w:
                count += 1
        if count == 1:
            yield word

def solution(begin, target, words):
    dist = {begin: 0}
    queue = deque([begin])

    while queue:
        current = queue.popleft()

        for next_word in get_adjacent(current, words):
            if next_word not in dist:
                dist[next_word] = dist[current] + 1
                queue.append(next_word)

    return dist.get(target, 0)

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.07ms, 10.2MB)
테스트 3 〉	통과 (0.81ms, 10.3MB)
테스트 4 〉	통과 (0.01ms, 10.3MB)
테스트 5 〉	통과 (0.01ms, 10.1MB)

• 와우? 이건 뭐지?

def solution(begin, target, words):
    answer = 0
    Q = [begin]

    while True:
        temp_Q = []
        for word_1 in Q:
            if word_1 == target:
                    return answer
            for i in range(len(words)-1, -1, -1):
                word_2 = words[i]
                if sum([x!=y for x, y in zip(word_1, word_2)]) == 1:
                    temp_Q.append(words.pop(i))

        if not temp_Q:
            return 0
        Q = temp_Q
        answer += 1
        
테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.11ms, 10.2MB)
테스트 3 〉	통과 (0.53ms, 10.1MB)
테스트 4 〉	통과 (0.01ms, 10.2MB)
테스트 5 〉	통과 (0.01ms, 10.2MB)

• 예쁘게 다듬 다듬 ㅎㅎㅎ

def solution(begin, target, words):
    answer = 0

    if target not in words:
        return answer
    
    words_bridge = {}
    for word in words: words_bridge[word] = 999
    words_bridge[begin] = 0
    
    for depth in range(len(words)):
        for key, value in words_bridge.items():
            if value == depth:
                for word in words:
                    if sum(1 for a,b in zip(word,key) if a != b) == 1:
                        if words_bridge[word] > depth + 1:
                            words_bridge[word] = depth + 1
                        if word == target: break

    return words_bridge[target]
    
정확성  테스트
테스트 1 〉	통과 (0.02ms, 10.2MB)
테스트 2 〉	통과 (0.12ms, 10.4MB)
테스트 3 〉	통과 (0.53ms, 10.2MB)
테스트 4 〉	통과 (0.02ms, 10.2MB)
테스트 5 〉	통과 (0.00ms, 10.3MB)