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

문제 설명

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

 

정답

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

    while True:
        temp_queue = []
        for word_1 in queue:
            
            if word_1 == target:
                    return answer

            for i in range(len(words)-1, -1, -1):
                word_2 = words[i]
                # word_1과 word_2의 철자 중 한글자만 같지 않다면
                if sum([x!=y for x, y in zip(word_1, word_2)]) == 1:
                    temp_queue.append(words.pop(i))

        if not temp_queue:
            return 0
        queue = temp_queue
        answer += 1

---

		if word_1 == target:
                    return answer

queue에 들어있는 word_1과 target이 같으면 탐색이 끝나므로

몇 단계 과정을 거쳤는지 저장한 answer를 return한다.

 

for i in range(len(words)-1, -1, -1):
                word_2 = words[i]
                # word_1과 word_2의 철자 중 한글자만 같지 않다면
                if sum([x!=y for x, y in zip(word_1, word_2)]) == 1:
                    temp_queue.append(words.pop(i))

단어의 집합 words의 마지막 단어부터 살펴보면서 word_2에 저장한다.

같은 위치의 word_2와 queue에서 꺼낸 word_1의 단어 철자가 다르다면 1을 반환하도록하여

단어의 처음부터 끝까지 살펴본 후 다 더했을 때 1이라면 철자가 하나만 다름을 의미한다.

이때 temp_queue에 해당 단어를 추가하는데

words.pop을 이용하여 다음번에 그 단어를 다시 살펴보지 않도록 word에서 없애준다.

 

	if not temp_queue:
            return 0
        queue = temp_queue
        answer += 1

만약 temp_queue가 비었다면 철자 하나만 다른 단어가 word에 없다는 뜻이므로

변환할 수 없다는 뜻이기 때문에 0을 return 한다.

그렇지 않다면 queue를 temp_queue로 바꾸고 한 단계를 거쳤으니 answer에 1을 더해준다.

 

이제 다시 queue에 있는 단어를 이용하여 위 과정을 반복한다.