728x90
😄 아이디어
1. _!words!_내 사용된 단어를 알파벳으로 변환하고 set 형태로 관리해, 변환 경우의 수를 최소화한다.
2. _!begin!_으로 DFS 시작, 변수로 주어진 단어는 첫 알파벳부터 _!set!_내의 글자로 바꿔가며 _!words!_내 존재확인
3. 존재하는 경우 _!visited!_의 값을 방문한 것으로 바꿔주고 다음 DFS 실행
4. 값이 최소값으로 변경되었다면 그대로 반환, 아니라면 0으로 반환
answer = 1_000_000_000
def solution(begin, target, words):
global answer
charset = set(char for word in words for char in word)
visited = [0 for _ in words]
count = 0
dfs(begin, charset, count, visited, target, words)
if answer == 1000000000:
answer = 0
return answer
def dfs(word, charset, count, visited, target, words):
if word == target:
global answer
answer = min(answer, count)
return
for c in charset:
for i in range(0, len(word)):
l = list(word)
l[i] = c
conv = ''.join(l)
if conv in words and visited[words.index(conv)] == 0:
visited[words.index(conv)] = 1
dfs(conv, charset, count + 1, visited, target, words)
visited[words.index(conv)] = 0