프로그래머스 - LV3. 단어 변환

문제

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

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

 

코드

1) BFS 이용

from collections import deque

def solution(begin, target, words):
    answer = 0
    
    if target not in words:
        return 0
    
    visited = [0] * len(words)
    queue = deque([begin])
    while queue:
        node = queue.popleft()
        if node == target:
            return answer
        for i in range(len(words)):
            if not visited[i] and node != words[i]:
                count = 0
                for j in range(len(begin)):
                    if node[j] != words[i][j]:
                        count += 1
                if count == 1:
                    queue.append(words[i])
                    visited[i] = visited[i] + 1
                    answer += 1
    
    return answer

정답이긴한데.. 테스트 케이스에서는 하나의 실패 케이스가 존재한다.

 

=> 아래 풀이는 둘 다 성공

 

 

 

 

 

 

2) BFS 이용

from collections import deque

def solution(begin, target, words):
    answer = 0
    
    if target not in words:
        return 0
    
    visited = [0] * len(words)
    queue = deque([[begin, 0]])
    while queue:
        word, count = queue.popleft()
        if word == target:
            answer = count
            break        
        for i in range(len(words)):
            temp = 0
            if not visited[i]:
                for j in range(len(word)):
                    if word[j] != words[i][j]:
                        temp += 1
                if temp == 1:
                    queue.append([words[i], count+1])
                    visited[i] = 1
                    
    return answer

queue에 count변수를 함꼐 저장하는 방식으로 풀 수 있구나!!!!@!!!!