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

아이디어 : 관건은 어떻게 한글자씩만 다른 단어를 찾을 것인가 + 최소의 단계만 거치도록 할 것인가. 인것 같다. BFS 유형인 것으로 추측해본다.

 

1) 한글자만 다른 단어의 pool을 찾고,

2) pool안의 각 단어에 대해서 동일한 작업을 반복하면...?

 

# 첫 번째 시도

from collections import deque

def is_substring_in_word(substring, word):
    i = 0  # substring 인덱스
    j = 0  # word 인덱스
    while i < len(substring) and j < len(word):
        if substring[i] == word[j]:
            i += 1
        j += 1
    return i == len(substring)

def solution(begin, target, words):
    answer=0
    last_word=''
    queue = deque([begin])
    if not target in words:
        pass
    else:
        while queue:
            print(queue)
            begin = queue[0]
            queue.popleft()
            for word in words:
                for i in range(len(begin)):
                    substring = begin[:i] + begin[i+1:]
                    if is_substring_in_word(substring, word):
                        queue.append(word)
                        words.remove(word)
                        last_word = word
                        if last_word==target:
                            queue.clear()
                            break
                        answer+=1
    if last_word!=target:
        answer=0
    return answer

 

오랫동안 고민을 해보았지만 여기서 answer 카운트를 어떻게 해야 할지 모르겠다. 분명... 한글자씩 바꿔서 타겟 단어까지 만드는 과정은 찾은 거 같은데, 타겟 단어로 가는 길이 아닌 경우의 단어들도 함께 카운트가 되는걸 어떻게 막을까?

 

최대한 비슷한 코드를 찾아서 어느 부분이 다른지 찾아보았다 -> https://jie0025.tistory.com/486

 

# 두 번째 시도

 

단계를 추가하여 step을 세는 방법이 좋은 것 같아 적용해보았다.

 

from collections import deque

def is_substring_in_word(substring, word):
    i,j = 0,0
    while i < len(substring) and j < len(word):
        if substring[i] == word[j]:
            i += 1
        j += 1
    return i == len(substring)

def solution(begin, target, words):
    answer = 0
    last_word=''
    queue = deque()
    steps = 0
    queue.append([begin,steps])
    
    if not target in words:
        pass
    else:
        while queue:
            begin, steps = queue.popleft()
            if begin==target:
                return steps
            for word in words:
                for i in range(len(begin)):
                    substring = begin[:i] + begin[i+1:]
                    if is_substring_in_word(substring, word):
                        queue.append([word, steps+1])
                        words.remove(word)
    answer = steps
    return answer

 

단, 이렇게 작성할 경우 런타임에러가 발생하는 경우가 생긴다. 따라서 count로 겹치는 단어를 세는 방법으로 바꾸었다.

 

from collections import deque

def solution(begin, target, words):
    answer = 0
    last_word=''
    queue = deque()
    steps = 0
    queue.append([begin,steps])
    
    if not target in words:
        pass
    else:
        while queue:
            begin, steps = queue.popleft()
            if begin==target:
                return steps
            for word in words:
                count = 0
                for i in range(len(begin)):
                    if begin[i]!=word[i]:
                        count+=1
                if count==1:
                    queue.append([word, steps+1])
                    words.remove(word)
    answer = steps
    return answer