greentea31's Note

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

풀이 과정

words 배열에 있는 단어 중, 현재 단어와 한 글자 차이 나는 단어로 이동이 가능하다고 할 때, begin에서 target까지 가는 가장 짧은 변환 과정을 구하는 문제이다. 변환이 불가능하면 0을 출력하면 된다.

이동 가능한 단어간의 거리는 1, 구해야 하는 것은 가장 짧은 경로.... 문제를 읽다보면 BFS가 바로 떠오른다. 이미 방문한 적이 있는 단어는 방문하지 않게끔 처리하면서 BFS로 단어들을 탐색하면서 거리를 측정하면 된다. 각 단어는 노드, 한 글자씩 차이나는 단어 노드들간에 간선이 존재하는 그래프로 생각할 수 있다.

어떤 진행 경로에서 방문하지 않았던 단어여도, 다른 진행 경로에서 방문한 단어면 방문 할 필요가 없다. 예를 들어 cat -> cot 경로가 존재하고 cat -> cet 경로에서 다음 단어를 찾는다고 가정해보자. BFS 진행 중, cat -> cet -> cot로 방문이 가능해야 하지만 어차피 이건 cat -> cot 경로보다 정답에 도달하는게 무조건 느리다. 따라서 방문을 할 필요가 없고, 다른 경로에서 이미 방문한 단어이므로 방문 불가능 처리를 해주면 된다. 즉, 경로마다 각자의 진행 경로를 저장할 필요 없이 어떤 경로에서든 이미 방문한 단어 노드이면 방문이 불가능하다고 생각해야 필요없는 경로를 구성하지 않으면서 답을 구할 수 있다.

소스 코드

import collections


discovered = []

def solution(begin, target, words):
    def transferable(a, b):
        same_char = 0
        length = len(a)
        for i in range(length):
            if a[i] == b[i]:
                same_char += 1
        if same_char == length-1:
            return True
        else:
            return False
    
    def bfs(start, words):
        Q = collections.deque()
        Q.append([start, 0])
        discovered = [False for _ in range(len(words))]
        
        while Q:
            cur_word, dist = Q.popleft()
            print(f'cur_word: {cur_word}, dist: {dist}')
            if cur_word == target:
                return dist
            for index, word in enumerate(words):
                if discovered[index]:
                    continue
                if not transferable(cur_word, word):
                    continue
                discovered[index] = True
                Q.append([word, dist+1])
        
        return 0
        
    
    if transferable(begin, target):
        return 1
    
    answer = bfs(begin, words)
    
    return answer