코드를 더 간결하게 줄일수있을듯 하다.
단어 하나를 그래프의 노드로 두고 각 단어별로 변환이 가능한 경우를 연결되었다고 생각하여 시작 단어를 포함하여 연결관계를 만든다.
시작 단어부터 시작하여 BFS를 돌면 Target으로 가는 최소 경로를 찾을 수 있게 되고
각 BFS를 수행할때마다 이전 경로까지의 길이 + 1이 되므로 해당 부분을 추가하면
쉽게 해답을 얻을 수 있다.
from collections import deque
answer = 0
visited = []
def bfs(graph, target, i, targetIdx, prev):
global answer, visited
visited[i] = True
if i == targetIdx:
answer = prev
return prev
for j in range(len(graph[i])):
if graph[i][j] == 1:
if visited[j]:
continue
bfs(graph, target, j, targetIdx, prev+1)
def solution(begin, target, words):
global answer, visited
if target not in words:
return 0
visited = [False]*(len(words)+1)
words = [begin] + words
graph = [[0]*len(words) for i in range(len(words))]
targetIdx = -1
for i in range(len(words)):
if words[i] == target:
targetIdx = i
for j in range(len(words)):
sum = 0
if i == j:
graph[i][j] =1
continue
for k in range(len(words[i])):
if words[i][k] != words[j][k]:
sum +=1
if sum == 1:
graph[i][j] = 1
bfs(graph, target, 0, targetIdx, 0)
return answer