두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때,
최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.
각 단어는 알파벳 소문자로만 이루어져 있습니다.
각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
begin과 target은 같지 않습니다.
변환할 수 없는 경우에는 0를 return 합니다.
begin | target | words | return |
---|---|---|---|
"hit" | "cog" | ["hot", "dot", "dog", "lot", "log", "cog"] | 4 |
"hit" | "cog" | ["hot", "dot", "dog", "lot", "log"] | 0 |
예제 #1
문제에 나온 예와 같습니다.
예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.
def solution(begin, target, words):
answer = 0
n = list(map(int, input().split()))
for i in words:
for n in begin:
words[i] == begin
words[j] == target
count += 1
return answer
def solution(begin, target, words):
answer = 0
n = map(int, input().split())
def DFS(i):
visited[i] = 1
for a in range(words):
if begin[i][a] and not visited[a]:
DFS(a)
visited = [0 for i in range(len(words))]
for i in range(words):
if not visited[i]:
DFS(i)
count += 1
return answer
from collections import deque
def solution(begin, target, words):
answer = 0
q = deque()
q.append([begin, 0])
V = [ 0 for i in range(len(words))]
while q:
word, cnt = q.popleft()
if word == target:
answer = cnt
break
for i in range(len(words)):
temp_cnt = 0
if not V[i]:
for j in range(len(word)):
if word[j] != words[i][j]:
temp_cnt += 1
if temp_cnt == 1:
q.append([words[i], cnt+1])
V[i] = 1
return answer
def solution(begin, target, words):
ans = 0
tmp = [begin]
visited = [0 for _ in words]
if target not in words:
return 0
while tmp:
stack = tmp.pop()
if stack == target:
return ans # dfs 탐색 후 최종 answer 리턴
for i in range(len(words)):
cnt = 0
for j in range(len(words[i])):
if words[i][j] != stack[j]: # 모든 단어 길이 같으므로 이렇게 체크
cnt += 1
if cnt == 1: # words[i] 체크해서 스펠링 하나만 다를 경우 체크
if visited[i] == 1: # 방문한 경우
continue
else:
visited[i] = 1 # 방문 안 한 경우
tmp.append(words[i])
ans += 1
return ans