프로그래머스: 단어 변환

문제

코딩테스트 연습 - 단어 변환

 

문제 풀이

 특정 단어가 주어질 때, 다른 단어와 비교하여 하나만 다른 경우에 그 단어로 변환할 수 있다. DSF를 통해 처음 시작하는 문자부터, 변활 할 수 있는 문자와 비교하여 두 문자가 하나만 다른 경우 해당 문자를 기준으로 탐색할 수 있는 과정을 반복한다. 이를 위해 `stack`을 이용하고, 중복을 막기 위해 `defualtdict`를 활용하여 방문 여부를 체크하였다. 

 

코드

from collections import defaultdict


def solution(begin, target, words):
    answer = 0
    stack = [begin]
    visited = defaultdict(bool)

    if target not in words:
        return answer

    while stack:
        cur_word = stack.pop()

        if cur_word == target:
            break

        for next_word in words:
            diff_cnt = 0

            if visited[next_word]:
                continue

            for c, n in zip(cur_word, next_word):
                if c != n:
                    diff_cnt += 1
                if diff_cnt > 1:
                    break
            else:
                visited[next_word] = True
                stack.append(next_word)

        answer += 1

    return answer

 변환 가능한 모든 단어를 stack에 추가하면, 한번의 시도가 끝난 것이므로 answer += 1을 해준다. stack의 단어가 target과 같다면,  더 이상 탐색을 진행할 필요가 없다.