[BFS] 단어 변환 - Level 3 (프로그래머스)

단어 변환

문제 소개

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

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

2. words에 있는 단어로만 변환할 수 있습니다.

   • 예를 들어 begin이 hit, target가 cog
   • words가 [hot,dot,dog,lot,log,cog] 라면
   • hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다.

target으로 도착하기까지 모든 횟수를 구하지 않고 최소로 변환할 수 있는 횟수만 필요하기 때문에 BFS를 사용했다.

• 예를 들어 dog라는 단어로 변환될 수 있는 단어들이 많으면 어떡하지라는 생각이 처음엔 들었다.
• 하지만 여러 방법이 있더라도 dog에서 cog로 한번만 변환하면 끝이기 때문에 dog로 가는 최소 단계를 찾아나가면 되었다. 이렇게 단계별 최소 단계만 찾아간다.

시나리오

1. 먼저, begin의 단어가 words의 단어로 교체 가능한 경우 큐에 현재까지의 횟수와 함께 push

   • begin과 words 단어의 다른 알파벳이 한 개일 경우에만 교체 가능
2. words의 길이와 같은 리스트를 생성하여 해당 word를 거쳐갔음을 0, 1로 구분
3. 반복문을 실행하며 begin과 target이 같으면 횟수를 반환, 답을 찾지 못하고 큐가 비어버리면 0 반환

문제 풀이

from collections import deque

def solution(begin, target, words):
    changed = [0 for _ in range(len(words))]
    que = deque()
    que.appendleft([begin, 0])

    while(que):
        begin, count = que.pop()
        
        if begin == target: 
            return count
        
        for w in range(len(words)):
            if not changed[w] and tf(begin, words[w]):
                changed[w] = 1
                que.appendleft([words[w], count+1])
                
    return 0

# 변환 가능 여부 확인
def tf(b, t):
    same = 0
    for i in range(len(b)):
        if b[i] == t[i]:
            same += 1
    if same == len(b)-1:
        return True
    return False

회고

BFS 구조 설계하는 시간이 빨라졌다.😎 다음 포스트에는 BFS와 DFS를 구분 짓는 유형을 찾아보려한다.