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

🔗

풀이

최단 거리를 구하는 그래프 탐색 유형의 문제라서 BFS로 풀었다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.

처음엔 두 문자를 set으로 변환한 다음에 차집합을 구하는 방식을 택했는데 이렇게 하면 중복되는 문자를 구별할 수가 없었다.

어차피 문자의 길이가 최대 10이기 때문에 브루트 포스로 하나씩 검사해도 연산 횟수가 최대 100을 넘지 않는다. a에 있는 문자가 b에 있다고 판단되면 b에서 그 문자를 제거 하고, 없다면 카운트를 1올려준다. 단 한 개의 문자만 달라야 하기 때문에 카운트가 2가 되는 순간 바로 False를 반환하는 방식.

def check(a, b):
    cnt = 0
    for char in a:
        if char not in b:
            cnt += 1
            if cnt > 1:
                return False
            continue
        b = b.replace(char, ' ', 1)
    return cnt == 1

def solution(begin, target, words):
    # BFS
    
    queue = deque([begin])
    visited = defaultdict(int)
    while queue:
        w = queue.popleft()
            
        for word in words:
            if visited[word] or not check(w, word):
                continue
                
            visited[word] = visited[w]+1
            if word == target:
                break
                
            queue.append(word)
        
    return visited[target]

from collections import deque, defaultdict