[프로그래머스] 단어 변환

문제링크

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

접근 방법

• 단어를 노드로, 문자를 바꾸는 것은 노드를 이동하는 것으로 본다.
• dog, log 처럼 문자 하나를 바꿔서 만들 수 있는 경우, 두 노드를 연결된 것으로 본다.
• is_connected 함수를 사용해 단어들의 연결을 찾고 그래프를 만든다.
• 이렇게 하면 문제를 최단거리를 찾는 문제로 볼 수 있게 된다.
• 가중치가 없는 그래프의 최단 거리를 찾으려면 BFS를 사용하면 된다.
• BFS는 큐를 사용한다.

코드 (python)

from collections import defaultdict, deque
from typing import List, Dict


def is_connected(a: str, b: str) -> bool:
    # 단어를 한글자씩 비교해서, 두 단어가 한 글자만 다르면 연결한다
    count = 0
    for i in range(len(a)):
        if a[i] != b[i]:
            count += 1

    return True if count == 1 else False


def solution(begin, target, words):
    words.append(begin)
    # key가 단어고 value는 연결된 단어 리스트인 딕셔너리를 만든다
    graph: Dict[str, List[str]] = defaultdict(list)
    for a in words:
        for b in words:
            if a == b:
                continue
            if is_connected(a, b):
                graph[a].append(b)

    # dfs로 target까지의 최단거리를 찾는다
    q = deque()
    q.append(begin)
    # begin 기준 몇칸 떨어져있는지 기록하기 위한 딕셔너리
    count: Dict[str, int] = defaultdict(int)
    count[begin] = 0

    while q:
        now = q.popleft()
        for next in graph[now]:
            # 아직 방문 안했다면 큐에 넣는다
            if count[next] == 0:
                q.append(next)
                # count를 현재 단어 기준 + 1 해서 갱신한다
                count[next] = count[now] + 1
                # 목적지에 도달해서 값을 갱신했다면 탐색 종료
                if next == target:
                    return count[target]
                
    # while문을 빠져나왔다면 target이 만들 수 없는 단어인 것
    return 0