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

난이도 : 레벨 3
유형 : BFS
출처 : https://school.programmers.co.kr/learn/courses/30/lessons/43163

문제 파악

두개의 문자열 begin, target 그리고 단어의 집합(배열) words를 준다.
begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾아야 한다.
변환할 때는 두가지의 규칙을 지켜야 한다.

1. 한번에 한개의 알파벳만 바꿀 수 있다.
2. words에 있는 단어로만 변환할 수 있다.

변환할 수 없는 경우 0을 return

해결 원리
처음에는 문자열을 숫자로 변환해서 풀어야 하나 싶었다.
그러나 이 문제는 인접 여부를 판단해서 BFS로 푸는 문제이다.
인접 여부는 한글자만 다른가? 가 된다.

고로 한글자만 다른지 판별해주는 함수를 따로 구현해야 한다.
한글자만 다른 지 판별하려면

1. 두 단어의 길이가 같아야 한다.
2. 각 자리 글자를 하나씩 비교하면서, 다른 글자가 몇 개인지 센다.
3. 다른 글자 수가 정확히 1개라면 → 한 글자만 다른 것

에 입각해 is_one_diff() 함수를 만들어주자.

from collections import deque
   
def solution(begin, target, words):

    # 두 단어의 길이가 같아야 한다.
    # 각 자리 글자를 하나씩 비교하면서, 다른 글자가 몇 개인지 센다.
    # 다른 글자 수가 정확히 1개라면 → 한 글자만 다른 것
    def is_one_diff(a, b):
        diff = 0
        if len(a) != len(b):
            return False
        for i in range(len(a)):
            if a[i] != b[i]:
                diff += 1
            if diff > 1:
                return False

        if diff == 1:
            return True
        else:
            return False
                                        
    # 큐 준비
    count = 0
    visited = [False] * len(words) # visited = [False, False, ...] 꼴이 됨

    # 시작 단어와 현재까지 변환 횟수를 큐에 넣는다.
    q = deque()
    q.append((begin,count))


    # BFS 진행
    while q:
    # 큐에서 단어를 꺼낸다.    
        curWord, count = q.popleft()

    # 그 단어가 목표 단어면 변환 횟수 반환.
        if curWord == target:
            return count
    
    # 아직 방문하지 않았고, 현재 단어와 한 글자만 다른 단어들을 큐에 추가한다.
    
        for i in range(len(words)):
            if visited[i] == False and is_one_diff(curWord, words[i]):
                visited[i] = True
                q.append((words[i], count + 1)) 
                         
                         
    return 0