https://programmers.co.kr/learn/courses/30/lessons/43163
프로그래머스 Lv3 단계답지 않게 꽤 간단한 문제였다.
begin에서 시작해서 target을 찾을 때 까지 words라는 트리를 순회하기만 하면 된다.
단어를 바꾸는 규칙은 간단하다.
조건1. 한번에 한 개의 알파벳만 바꿀 수 있다.
조건2. words에 있는 단어로만 변환할 수 있다.
words 배열 속 word를 살펴보면서 현재 단어인 now와 한 개의 알파벳을 제외한 나머지가 일치하는 word를 찾아나가다가 target과 일치하는 word를 발견하면 break하면 됐다.
그래서 먼저 한 개의 알파벳을 제외한 나머지가 일치하는 word를 찾는 함수인 coincide()를 만들었다.
def coincide(a, b):
cnt = 0
for i in range(len(a)):
if a[i] != b[i]:
cnt += 1
return 1 if cnt == 1 else 0
coincide()를 돌리면서 조건1을 만족하는 word를 찾기 전에 일단 target이 words 배열에 없으면 문자를 변환할 수 없으니까 일단 target이 words에 존재하지 않을때 solution 함수를 return 0해주는 코드를 초반에 넣어주었다.
stack을 사용해서 dfs를 돌렸다.
아래 표와 같은 과정을 거쳐서 concide()의 return이 1인 word는 stack에 append하고 depth (코드에서는 answer)를 늘려가면서 target을 찾다가 target과 일치하면 while문을 빠져나온다.
전체적인 solution의 소스코드는 아래와 같다.
def solution(begin, target, words):
answer = 0
if target not in words:
return 0
stack = [begin]
visited = {begin : 0}
for word in words:
visited[word] = 0
# DFS
while stack:
now = stack.pop()
if now == target:
return answer
if not visited[now]:
visited[now] = 1
for word in words:
if coincide(now, word):
stack.append(word)
answer += 1
return answer