[코딩테스트] 프로그래머스 - 단어 변환 (Lv.3) in Python

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환 가능한 지 알려주는 solution 함수 구현

 

 

 

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

 

풀이과정은 프로그래머스 수업 내용을 바탕으로 합니다.

 

풀이

- 너비 우선 탐색 (BFS)를 사용해서 풀면 효율적이다.

- 너비 우선 탐색은 FIFO (선입선출) 로직을 사용하므로, 큐 자료구조가 적합하다.

(참고 - 여행 경로 문제 (piaflu.tistory.com/62 )

 

 

# 비교할 두 단어가 변환 가능한 지  - 한 글자만 다름 - 확인
def possible(start, target):
    count = 0
    for i in len(start):
        if start[i] != target[i]:
            count += 1
        if count ==2:
            return False
    return True

from collections import deque
# solution
def solution(begin, target, words):
    visited = {begin: 0} # 각 단어에 이르기까지 필요한 스텝 수
    
    q = deque([begin])

    while q:
        curr = q.popleft()
        for word in words:
        	# 탐색하는 단어가 아직 visited에 포함 안 되었으며 curr단어에서 변환 가능하면
            if word not in visited and possible(curr, word):
            	# 현재 탐색하는 단어에 이르기까지 스텝 수는, curr단어에 이르기 까지의 단계수 + 1
                visited[word] = visited[curr]+1
                q.append(word)

    if target in visited:
        return visited[target]
    return 0