프로그래머스 - 단어 변환(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 합니다.

입출력 예begintargetwordsreturn

"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

 

나의 풀이

from collections import deque


def solution(begin, target, words):
    if target not in words:  # 애초에 words리스트에 target값이 없다면 return 0
        return 0
    
    q = deque()
    q.append([begin, 0])
    
    while q: # bfs 방식으로 모든 연결 조건에 맞게 트리 만들고, 해당하는 층에 cnt를 반환하는 방식
        w, cnt = q.popleft()
        
        if w == target:
            return cnt
        
        for i in range(len(words)): #해당 단어의 한개 글자만 차이나는 글자를 묶어주는 작업
            diff = 0
            word = words[i]
            for j in range(len(w)): 
                if w[j] != word[j]: #한개만 다른지 확인하기 위해, 다르면 q에 어펜드
                    diff += 1
            if diff == 1:
                q.append([word, cnt + 1])
                
    #target이 words에는 있지만, 반환이 안되는 경우    
    return 0

트리 구조를 생각해서 target이 있는 층을 반환하면 된다.

 

1) 너비 우선 탐색으로 타겟이 있는 층까지 탐색 후 스탑

 

2) 우선 해당 타겟이 없을 때는 바로 0을 반환

 

3) 타겟이 words안에 있을 때, 있어도 반환이 안될 때는 0을 리턴

 

4) bfs는 큐 자료구조를 활용하여 터널 구조로 먼저 들오온 녀석을 빼내고 확인하고를 계속 반복!

 

5) 시작 노드와 해당 노드의 층 0 을 넣고 시작

 

6) 해당 값이 타겟이면 스탑하고 그 층이 cnt가 리턴

 

7) 처음 노드와 모든 노드의 값들을 비교하고 해당 노드에 연결되는 즉, 한 글자 빼고 모두 같은 조건에 해당하는 단어를 연결(단어와 단어가 있는 트리에서의 층을 어펜드)

 

8) 7번을 반복하여 다음 층에 노드들과 연결 되어있는 노드를 또 찾아 연결 ! 

 

9) 해당 타겟이 나올 때 까지 반복

 

* bfs는 방문한 노드에는 다시 방문 안하도록 하는 조건이 있지만, 위 알고리즘은 bfs와 비슷한 방식으로 그래프를 만드는 과정에서 찾을 수 있어 해당 조건은 여기서는 사용하지 않았다. 아래는 그래를 통해 bfs탐색을 하는 코드이다.

def bfs(graph, start_node):
	visit = list()
    queue = list()
    
    queue.append(start_node)
 
     while queue:
         node = queue.pop(0)
         if node not in visit:
             visit.append(node)
             queue.extend(graph[node])

     return visit

 

다른 사람의 풀이

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)

이 분의 코드를 보며 제너레이터 함수를 잘 활용했다고 생각이 들었다. 제너레이터 객체의 장점은 메모리 할당량이 일정하여 원소의 크기가 아무리 커도 일정량을 벗어나지 않는다는 장점이 있다. 왜냐면 필요할 때만 yeild해주는 시스템이니까!

그리고 제너레이터 함수도 아이터레이터 객체이므로 반목문으로 쓰일 수 있다.