단어 변환

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

🤔생각해보기

처음엔 문제를 보고 살짝 당황했다. 문자를 하나하나 모두 체크하라는건지 도대체 이걸 어떻게 풀어야하나...

그래서 그림으로 그려봤다.

 

 

이런 모양의 그래프가 그려지며,

그림을 보면 반대편 끝에 있는 "cog" 가지 도달하기 위한 깊이를 세어주면 되겠다는 느낌이 든다.

그래프를 그려보면 알게되지만, 결국 모든 스펠링의 검사가 필요하다.

알고리즘을 순서대로 적어보자면,

• 거리를 알기 위해 BFS 를 이용하여 각 노드의 이름과 거리를 함께 저장할 것이다.
• 다음 방문할 노드를 알기 위해 스펠링을 체크하여 현재 노드와 1개만 다른 단어를 다음 노드로 추가한다. 이미 방문했던 노드라면, 추가하지 않는다.
• 방문해야할 노드가 담긴 리스트에서 하나씩 꺼낼 때, target 이 등장한다면 함께 저장된 count 를 return 한다.

성공

from collections import deque


def solution(begin, target, words):
    if target not in words:
        return 0

    queue = deque([(begin, 0)])
    visited = []

    while queue:
        n, count = queue.popleft()

        # queue 에서 target 이 등장한다면 저장된 count 를 return
        if n == target:
            return count

        visited.append(n)

        # 다른 부분 검사 후 목적지 추가
        for w in words:
            diff = 0
            for i in range(len(w)):  # 모든 단어의 길이는 같다.
                if n[i] != w[i]:
                    diff += 1
            if diff == 1 and w not in visited:  # 다른 단어가 하나뿐이고 방문한 적이 없다면, 목적지에 설정, 전 노드의 카운트 + 1
                queue.append((w, count + 1))

더 좋은 코드를 위한 고민들

• 스펠링 체크 부분은 zip() 을 사용할수도 있다.
• 이미 방문한 곳의 단어는 스펠링을 검사할 필요가 없다. 하지만 문제 조건의 개수가 적기 때문에 O(N^2)의 시간복잡도를 감수해도 되었다.