프로그래머스 43163 단어 변환 파이썬 풀이

난이도 : Lv. 3

풀이일 : 2411144

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

프로그래머스

---

문제

---

아이디어

• BFS로 탐색한다.
• queue를 사용해서 현재 단어와 현재까지의 변환 횟수를 저장한다.
• words 안의 모든 단어에 대해 현재 단어와 몇 글자가 다른지 비교 작업을 한다.
• 현재 단어와 한 글자만 다른 단어로 변환하고, 변환 단어와 변환 횟수를 queue에 추가한다.
• 목표단어에 도달할 경우, 변환 횟수를 반환하고, 끝까지 도달하지 못하면 0을 출력한다.

---

풀이 코드

from collections import deque

def solution(begin, target, words):
    answer = 0
    visited = [False] * len(words) # 방문여부 확인
    queue = deque()
    queue.append((begin, 0)) # 최초 단어, 변환횟수
    
    while queue:
    	# 현재단어, 현재까지 변환횟수
        before, count = queue.popleft()
        for i in range(len(words)):
            after = words[i]
            miss = 0 # 다른 알파벳 수
            for j in range(len(after)):
                if before[j] != after[j]:
                    miss += 1
            # 한 단어만 다르고, 방문하지 않은 단어일 경우
            if miss == 1 and not visited[i]:
            	# 현재 단어가 목표단어일 경우
                if after == target:
                    return count + 1
                queue.append((after, count + 1))
                visited[i] = True
    
    return answer

• visited : 각 단어의 방문 여부를 확인
• queue : (현재단어, 현재까지의 변환횟수) 를 저장
• before, count : 변환 전 현재 단어, 현재까지의 변환 횟수
• after : 변환이 가능한지 검사하는 단어
• miss : before, after의 다른 알파벳 개수
• for j in range(len(after)) : before와 after의 각 자리 알파벳 비교 후, 다르면 miss 증가
• 다른 글자가 한 개 뿐이고, 아직 방문하지 않은 단어라면 방문
• 변환할 단어가 목표 단어라면, 현재까지의 변환 횟수 + 1 반환
• 변환할 단어가 목표 단어가 아니라면, 변환한 새 단어, 변환횟수를 queue에 추가하고 방문 표시

---

느낀점

• 원래는 miss가 1을 초과하였을 때 before와 after의 알파벳 비교를 중단하는 부분을 넣었었는데, 결과에서 별로 차이가 없어서 제거했다.
• 조금 더 쉽고 예쁘게 풀 수 있는 방법이 있을 것 같은데 뭐가 없을까 고민해봐야지