문제 링크 및 문제 내용

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

문제 설명

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

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

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

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

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

풀이 코드

# dfs/bfs '단어변환'
from itertools import combinations
from collections import deque
import queue
import re

def bfs(begin, target, words, distance):
     # 변수1 타겟이 찾으려는 문자리스트에 없을때
    if target not in words:
        return 0

    # begin값 큐에 넣어주고 distance 리스트에 초기값 넣어줌.
    queue = deque([begin])
    distance[words.index(begin)] = 0
    
    while queue:    # 큐가 빌때까지
    
        alp = queue.popleft()
        # 타겟값을 구했을때 리턴
        if alp == target:
            return distance[words.index(target)]
        # 변경 가능한 리스트 반복
        for word in words:
            check = 0   # 카운팅 저장값 변수
            # 글자 수만큼 반복해주면서 해당 인덱스의 값이 같은 경우 카운팅
            for i in range(len(alp)):   
                if word[i] == alp[i]:
                    check += 1
            # 변경 가능한 글자일때
            if check == len(word) - 1:
                # 해당 거리 값이 0일때 큐에 넣어주고 거리 추가 * 0 = false
                if not distance[words.index(word)]:
                    queue.append(word)
                    distance[words.index(word)] = distance[words.index(alp)] + 1
            
                           
        
def solution(begin, target, words):
     # 정답 카운트
    distance = [0] * (len(words) + 1)  # 방문기록
    words.append(begin) # begin을 words에 넣어줘서 거리로 계산으로 바꿨습니다.
    
	# 출력 
    answer = bfs(begin, target, words, distance)
    return answer

이렇게 풀었어요🔍

1. bfs를 사용하자 ( hit -> hot -> dot, lot -> ....)
2. hit->hot 처럼 h t 의 두글자가 같을때 큐에 넣어주고 방문처리
3. 글자 값을 경우의 수 처리(combinations) 하려했으나(실패..후) 인덱스로 카운팅 처리

발생했던 문제점🤣

1. combinations를 사용해서 경우의 수를 넘겨줬을때 hhf -> hfh 로 변환시
   경우의 수가 ('h','h'), ( 'h','f' )가 나오는데 인덱스까지 같아야 했기 때문에 문제가 되었고, 문자열의 인덱싱도 생각해 작성하였습니다.

        for word in words:
            check = 0   # 카운팅 저장값 변수
            # 글자 수만큼 반복해주면서 해당 인덱스의 값이 같은 경우 카운팅
            for i in range(len(alp)):   
                if word[i] == alp[i]:
                    check += 1  

2. 처음 풀이로는 원래 distance 리스트가 아니라 visitded 리스트로 방문여부를 boolean을 통해 확인하게 처리하였고, 제가 작성한 bfs에서는 hit-> hot 나 hot -> dot, lot 처럼 해당 사이클에 카운트를 해줘야하는데 그 처리가 어려웠고, boolean 방식에서 거리 방식으로 해결했습니다.