[Python] 프로그래머스 - 단어변환

프로그래머스 - 단어변환 / 문제 유형 : bfs / Level 3

 

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

프로그래머스

 

저번에 이어 계속 고득점 Kit BFS/DFS 를 푸는 중이다.

 

문제를 간단히 요약하면, 시작 단어를 주어진 배열 안 단어로 바꾸면서 target을 찾는 문제이다.

target을 찾기위해 변환한 횟수를 구하면 되고, 현재 단어와 1글자만 다른 단어만 바꿀 수 있다는 조건이 있다. 

자세한 설명은 사진과 링크를 확인하면 된다.

 

Solution

1. 인접리스트를 생성한다.

 

     인접리스트는 주어진 배열 안에 있는 단어들중 서로 1개 차이만 나는 단어들의 인덱스를 저장해 놓은 리스트 이다.

     위의 문제로 예를 든다면,

 

     [hot, dot, dog]  
    -> hot : dot,                // 인덱스 변환  0 : 1
         dot : hot, dog        //                     1 : 0,2

     이런 식으로 바꿀 수 있는 단어들의 정보를 저장해 준다.

     저장하기 쉽게 인덱스로 저장하였다.

 

2. 인접리스트를 돌면서, 원하는 타겟을 찾는다.

 

    이때, 변환된 횟수를 저장하기 위해 d라는 변수를 넣어 주었고, 변환 될 수록 d+1을 저장하였다.

    인접리스트를 생성할 때, 시작 단어를 0번째에 넣어서 만들어 주었으므로, 0번부터 시작하면 된다.

     만일, target을 찾았으면, 현재까지 변환된 횟수를 return하고,

    찾지 못했으면, 0을 반환한다

 

 

Answer

from collections import deque

def solution(begin, target, words):
    answer = 0
    len_word = len(begin) #단어 길이
    word_data = [] # 인접리스트
    words.insert(0,begin)
    visited = [False] * len(words)

    # 1문자 차이인 인접리스트 생성
    for i in range(len(words)):
        data = []
        w1 = list(words[i])
        for j in range(len(words)):
            w2 = list(words[j])
            num = 0
            for i in range(len_word):
                if w1[i] != w2[i]:
                    num += 1
            
            if num == 1:
                data.append(j)
                
        word_data.append(data)
    
    #인접리스트를 bfs 진행
    def bfs(start, word_data, visited,target):
        
        visited[start] = True
        
        queue = deque([(start,0)]) # 시작 인덱스, 바뀐 횟수
        
        while queue:
            x,d = queue.popleft()
            
            for g in word_data[x]:
                #타겟이 있다면 거리+1을 반환
                if words[g] == target:
                    return d+1
                if not visited[g]:
                    #방문하지 않았다면 바꾼횟수 +1을 넣어줌
                    visited[g] = True
                    queue.append((g,d+1))
        return 0
        
    answer = bfs(0,word_data,visited,target)
    
    return answer

 

 

 

질문이나 궁금하신점 또는 제가 잘못 알고있는 정보는 댓글 부탁드립니다😊