문제
문제 설명
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
- 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
- words에 있는 단어로만 변환할 수 있습니다.
예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.
두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.
제한사항
각 단어는 알파벳 소문자로만 이루어져 있습니다.
각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
begin과 target은 같지 않습니다.
변환할 수 없는 경우에는 0를 return 합니다.
접근
begin 단어에서 시작하여 해당 target 단어로 도달하는 최단 경로를 찾는 완전탐색 문제. 보통 완전탐색 문제는 DFS/BFS, 백트래킹을 사용하여 해결할 수 있다. 나는 DFS 방식을 사용하여 문제를 해결하였다.
DFS 를 구현하는 방법에는 2가지가 존재한다.
첫번째는 스택을 이용하는 방법
두번째는 재귀함수를 이용하는 방법
DFS는 트리의 깊이가 깊어질수록 실행시간이 기하급수적으로 늘어나기 때문에, 깊이를 예측하기 쉽거나 처리해야할 계산량의 크기가 많지 않을때 사용하는 것이 좋다.
위 문제는 단어의 길이가 최대 10, words 배열의 크기가 최대 50 (최대 깊이 50) 으로 데이터의 양이 많지 않기에, DFS 방식으로 충분히 해결 가능하다.
매개변수로 전달된 두 단어가 한글자만 차이나는지 확인하는 함수
def can_change(first,second):
count=0
for i in range(len(first)):
if first[i]!=second[i]:
count+=1
if count==1:
return True
else:
return False
def solution(begin, target, words):
visit_dict={}
for word in words:
visit_dict[word]=0
stack=[]
stack.append([begin,0])
while stack:
cur=stack.pop()
if cur[0]==target:
return cur[1]
for word in words:
if can_change(cur[0],word) and visit_dict[word]==0:
visit_dict[word]=1
stack.append([word,cur[1]+1])
return 0프로그래머스 선정 난이도와 정답률에 비해 굉장히 많이 해맸던 문제.
아마 DFS/BFS에 대한 부족한 이해 떄문에 그랬던것같음. 다른 문자의 갯수가 1인 문자로 변환 가능하다는 것은 곧 가중치가 1인 그래프에서 다른 정점으로 가는 것과 동일하며, 즉 이 문제는 최단 거리 계산 문제와 같은 문제라고 볼 수 있다. index로 이루어진 정점이 아니더라도 dictionary를 사용하면 visit 처리를 해줄 수 있다.
