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

Programmers 단어 변환

코드

from collections import deque

def solution(begin, target, words):
    
    if target not in words:
        return 0
    else:
    
		    // 큐에 현재 단어와 변환 횟수를 저장
        queue = deque([(begin, 0)])
        visited = set([begin])
        
        while queue:
            current_word, step = queue.popleft()
            
            // 현재 단어가 target과 일치하면 변환 횟수를 return
            if current_word == target:
                return step
            
            // 다음 단계로 가능한 모든 단어를 queue에 넣음
            for word in words:
                if word not in visited:
                
		                // 알파벳이 1개 다른지 확인
                    diff_cnt = sum(c1 != c2 for c1, c2 in zip(word, current_word))
                    if diff_cnt == 1:
                        visited.add(word)
                        queue.append((word, step + 1))
        
    return 0

풀이 과정

두 단어가 한 글자만 다르면 연결되어 있는 단어 그래프 문제이므로, queue를 이용하는 BFS를 사용하여 풀어야겠다고 생각했다.

그리고 위 문제와 같이 모든 이동 비용이 1인 최단 거리를 구하는 문제는 BFS가 잘 맞는다고 한다.

또한 DFS를 사용할 수도 있지만 그 경우에는 더 긴 경로가 있으면 그걸 먼저 찾을 수도 있기 때문에, target을 처음 만났을 때 최소를 보장하지 못하게 된다.

따라서 DFS 사용은 더 번거롭고 비효율적일 수 있다고 생각했다.

BFS에서는 ‘먼저 들어온 것을 먼저 꺼낸다.’와 같은 구조를 사용하기 때문에 양쪽에서 빠르게 넣고 뺄 수 있는 자료구조인 queue를 사용한다.

결과적으로 단어를 탐색하여 단어를 변경한 횟수를 반환해야되므로, 튜플을 사용하여 현재 단어와 변환 단계 수를 묶어서 queue에 저장하였다.

• 튜플 (tuple): 여러 값을 하나로 묶는 자료구조

• deque( [ (begin, 0) ] ) → 차례대로 deque 함수 호출, 리스트, 튜플을 사용하는 괄호를 의미한다.

visited에는 이미 방문한 단어를 저장하기 위해 set 집합을 사용하였다.

• set 집합: 중복을 허용하지 않아서 방문 체크에 자주 사용

다음 변환 단어를 탐색하기 위해 튜플 언패킹을 했다.

• 튜플 언패킹: 코드에서처럼 튜플로 저장한 두 값을 두 변수에 나눠 담음
  current_word, step = ("hit", 0)

두 문자열을 비교하여 알파벳이 1개만 다른지 확인하기 위해 zip()을 사용했다.

• zip(): 각각 비교 문자열을 앞에서부터 하나씩 묶어줌
  zip(word, current_word) → ('h', 'h')

• for c1, c2 in zip(word, current_word)
  → zip으로 묶인 글자 쌍을 하나씩 꺼내서 씀

• diff_cnt = sum(c1 != c2 for c1, c2 in zip(word, current_word))
  → word와 current_word를 한 글자씩 비교해서 다른 글자의 개수를 세도록 함

  h == h → False -> 0

  o != i → True -> 1

최종적으로 코드에서 BFS는 0단계 단어 전부 확인 → 1단계 단어 전부 확인 → 2단계 단어 전부 확인 → … 순서로 탐색하여 짧은 거리부터 먼저 다 확인하게 된다.

따라서 처음 만난 step이 최소 변환 횟수가 될 수 있다.