프로그래머스(programmers) 단어 변환 python 정답[BFS 풀이]

프로그래머스(programmers) 단어 변환 python 정답[BFS 풀이]

문제 링크

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

프로그래머스

문제 정답

입출력 예

def solution(begin, target, words):
    answer = 0
    Q = [begin]
    used = {begin : True}

    while Q:
        # 다음 번에 순회할 큐를 만든다
        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 isTransformable(word_1,word_2) and not word_2 in used:
                    next_word = words[i]
                    used[next_word] = True
                    temp_Q.append(next_word)
        # 반환할 수 없는 경우
        if not temp_Q:
            return 0        
        Q = temp_Q
        answer += 1

def isTransformable(word_1,word_2):
    return sum([x!=y for x, y in zip(word_1, word_2)]) == 1

문제 해설

그래프 탐색과 유사한데, 그래프를 미리 만들어두거나 하지 않는다.

해당 문제는 Q를 두개 만드는데,

• 첫번째 Q에 있는 모든 대상에 대한 순회를 하면서 Q를 조작하면 레이스 컨디션에 의한 버그가 발생할 수 있으며,
• 해당 큐를 비우고(모두 순회하고) 다음 큐로 가면서 "단계"를 체크하기 떄문이다.

솔직히 어려운 문제는 아니지만, isTransformable 부분에서 헷갈렸는데,

본인은 문제를 잘못 이해하여 순서를 체크하지 않았기 떄문이다.

아래와 같이 나머지 요소들이 동일할 때, 인덱스도 같아야 한다.

# h i t
# V X V
# h o t

해당문제는 어떻게 보면 큐를 계속 inque, deque하는게 아니라,

다음 배열... 다음 배열 이런 식으로 단계적으로 스탭을 밟아가는 느낌이라

dfs로 표현하는것도 나쁘지 않아보인다.

 

구현은 아래와 유사하게 하면 될테니 연습해보자.

def dfs(q,used):
	# 구현
    
# ...
dfs([begin],{begin:True})