프로그래머스_단어변환

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

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

이 문제는 DFS, BFS 두 알고리즘이 가장 먼저 떠올랐지만 최단거리가 문제의 주요 핵심인 만큼 Dijkstra(다익스트라)를 써야겠다고 생각 들었다. 물론 DFS, BFS로 구현이 불가능한 것은 아니지만 다익스트라 구현이 더 끌렸다..ㅎ

◎ Code

import numpy as np

def solution(begin, target, words):

    words[1:] = words
    words[0] = begin
    relation = list(np.zeros(len(words)**2).reshape(-1,len(words)))

    for i in range(len(words)) :
        for j in range(i+1, len(words)) :
            cnt = 0
            for k in range(len(begin)) :
                if words[i][k] != words[j][k] :
                    cnt += 1
            if cnt <= 1 :
                relation[i][j] = 1
                relation[j][i] = 1
    
    check = [False for _ in range(len(words)+1)]
    steps = [99 for _ in range(len(words))]

    def bfs(index, step) :
        check[index] = True
        steps[index] = step
        for i in range(len(words)) :
            if relation[index][i] == 1 and steps[i] > step :
                bfs(i, step + 1)

    bfs(0, 0)

    try :
        target = words.index(target)
    except ValueError :
        target = 0 
    finally :
        return steps[target] if target != 0 else 0

 

◎ Code 설명

- 기본적으로 Dijkstra로 구현한 만큼 변할 수 있는 단어 끼리의 간선의 가중치를 1로 지정하고 시작한다.

- 시작 노드는 begin 노드이므로 begin을 0번쨰 노드로 지정한다

- 0번째 노드를 시작으로 최단거리 알고리즘(Dijkstra)를 진행한다

- 만약 현 단어에서 변할수 있는 단어인데 더 짧은 거리로 도달했다면 거리의 값을 갱신한다.

- 모든 과정이 끝난 후 target노드의 값에는 최단거리가 저장되있을 것이다.

- try문을 사용한 이유는 만약 target이 words 리스트에 없을 경우를 위함이다.(없을 경우 변할 수 없으므로 0)

- finally문에 삼항연산자를 이용한 이유는 target의 값이 0인경우 0을 출력해야 하기 때문이다.