[🥲 프로그래머스] 단어 변환 - BFS/DFS

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

코딩테스트 연습 - 단어 변환

 

✅ 내가 시도한 풀이

from collections import deque
def solution(begin, target, words):

	# 그래프 생성
    words.append(begin)
    graph = {i:[] for i in words}
    for i in range(len(words)-1):
        for j in range(i, len(words)):
            count = 0 
            for k in range(len(words[i])):
                if words[i][k] != words[j][k]:
                    count += 1
            if count == 1:
                graph[words[i]].append(words[j])
                graph[words[j]].append(words[i])
    
    
    # 로직
    # 같은 깊이에 있는 애들을 다 탐색하면 answer +1 
    queue = deque([begin]) # 시작
    visited = [] # 방문 리스트
    answer = 0

    while queue:
        temp = deque([]) # 새로운 queue가 될 temp
        for q in queue: # q를 하나씩 뽑아서
            if q == target: # target이랑 같으면 끝
                return answer
            if q not in visited: 
                visited.append(q)
                temp.extend(graph[q])
        answer += 1 
        queue = temp
    
    return 0

 

 

✅ 다른사람 풀이

def solution(begin, target, words):
    answer = 0
    queue = [begin]
    
    while True:
        tmp_q = [] # 같은 레벨의 단어를 집어넣는다
        print(queue)
        for word_1 in queue:
            if word_1 == target:
                return answer
            for word_2_idx in range(len(words)-1, -1, -1): # 오류없이 pop 사용을 위해
                word_2 = words[word_2_idx]
                difference = sum([x != y for x, y in zip(word_1, word_2)]) # 틀린 글자수 차이
                if difference == 1: # 한글자만 다르면
                    tmp_q.append(words.pop(word_2_idx)) # temp에 집어넣는다.
        if not tmp_q:
            return 0
        queue = tmp_q
        answer += 1

리스트를 거꾸로 탐색하면 pop시 오류가 나지 않는다!!!!