[Programmers] 깊이/너비 우선 탐색 > 단어변환

[Programmers] 깊이/너비 우선 탐색 > 단어변환

안녕하세요 이번에는 Programmers 깊이/너비 우선 탐색 문제 중에 단어변환이라는 문제를 풀어보겠습니다.

출처:

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

풀이

def solution(begin, target, words):
    answer = 0
    
    stack = [begin,]
    visited = []
    
    while stack:
        n = stack.pop()
        list_n = list(n)
        if n not in visited:
            visited.append(n)
            for st in words:
                count = 0
                list_st = list(st)
                for i in range(len(list_n)):
                    if list_n[i] == list_st[i]:
                        count += 1
                if count == (len(list_n) - 1):
                    stack.append(st)
    
    if target in visited:
        answer = visited.index(target)
    else:
        answer = 0

    return answer

해당 문제는 문자열을 비교하면서 깊이 탐색으로 해결했습니다. 각 단어들을 List에 담아서 1가지 문자만 다른 경우에만 Stack에 넣는 방법을 선택했으며 DFS를 이용하여 탐색을 진행했습니다. 또한 마지막에 만약 단어 변환이 불가능하다고 하면 0을 return 해야하는 조건을 만족시켜주기 위하여 코딩을 했습니다.

다른 사람들 풀이 리뷰

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)

탐색의 효율을 높이기 위해서 Stack이 아닌 queue를 이용하는 모습이다. 그리고 단어의 비교를 Zip을 이용해서 단어끼리 다른 문자가 1개가 카운팅 될때 yield를 이용해서 해당 단어를 리턴하는 모습을 보여준다. 또한 dictionary를 이용해서 단어의 시작부터 target을 만나는 순간까지 카운팅해주는 코딩을 보여줬다.

느낀점

dfs를 이용할때에는 queue를 이용하는 습관을 길러야하며 단어와 단어를 비교할 때 각각을 list로 만들 필요없이 zip(word1, word2) 를 이용해서 반목문을 돌린다면 된다는 것을 깨달았다.

여기서 파이썬 내장함수인 zip()은 같은 길이의 리스트를 같은 인덱스끼리 잘라서 리스트로 반환해주는 역할을 한다.