문제
접근
변환 가능한 단어의 경로를 따라가면서 target에 가장 빨리 도달하는 방법을 찾는 문제이다.
BFS 알고리즘을 이용하면 쉽게 탐색 가능하다.
아예 전처리해서 그래프 형식으로 만들어놓고 탐색할까 하다가 그렇게까지 안해도 될거같아서,
그냥 단어 전체를 보며 다음 경우의 수를 탐색했다.
isConvertPossible 함수는 주어진 두 개의 단어가 변환가능한 단어인지 확인하는 함수이다.
이 때, 내 코드의 특성상 주어지는 두 단어가 같을 수도 있다.
따라서 같은 경우 굳이 변환할 필요가 없으므로, False로 처리해주었다.
현재 단어에서 이동가능한 단어들을 stack에 담아준다.
그리고 스택에서 하나씩 빼가며 다음 경로를 탐색하는 방식이다.
BFS 알고리즘의 특징 중 하나가 이전에 방문한 경로는 무조건 최소 길이가 보장된다.
stack의 특성 때문이랄까, 그래서 방문 표시가 되어있으면 해당 경로는 더이상 방문할 필요가 없다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def solution(begin, target, words):
answer = 0
visit = [0] * len(words)
if not target in words:
return 0
stack = [(begin, 0)]
while stack:
nowWord, nowDis = stack.pop()
if nowWord == target:
return nowDis
for i in range(len(words)):
if isConvertPossible(nowWord, words[i]) and visit[i] == 0:
visit[i] = nowDis+1
stack.append((words[i], nowDis+1))
return 0
def isConvertPossible(nowWord, target):
cnt = 0
for a,b in zip(nowWord, target):
if a != b:
cnt += 1
if cnt == 1:
return True
else:
return False