📃 문제 링크
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.
제한사항
입출력 예
begin | target | words | return |
---|---|---|---|
hit | cog | [hot, dot, dog, lot, log, cog] | 4 |
hit | cog | [hot, dot, dog, lot, log] | 0 |
스택을 이용한 DFS로 풀었다.
먼저 visited
리스트로, words
리스트의 요소를 방문했다는 상태를 저장했다.
현재 단어는 current_list
에 저장하고, 스택으로 사용해 pop()
으로 현재 단어를 꺼낸다. 현재 단어와 words
의 단어를 하나씩 비교하여 한 개의 알파벳만 다르다면, visited
에 방문했다고 표시해주고 바꾼 현재 단어를 스택에 다시 추가한다.
한 글자만 다른 단어가 words
에 여러 개 있을 수 있지만, 그 중에 하나만 선택할 것이기 때문에 words
리스트 탐색을 모두 끝낸 후 answer
를 1 올려준다.
반복문을 돌면서 현재 단어가 target
과 같다면 answer
를 리턴한다.
target
이 words
리스트에 없는 경우, 아예 변환할 수 없는 경우이기 때문에 0을 return하는 예외를 처리해준다.
현재 단어로 target
까지 달성할 수 있는지 끝까지 갔다가 돌아오기 때문에 DFS!
먼저, 코딩테스트 연습하는데 많은 도움을 받고 있습니다. 친절한 풀이 정말 감사합니다!
그런데 본 문제의 코드가 테스트 케이스는 전부 통과하는데, 문제가 좀 있는 것 같습니다.
예를 들어, begin "aaa", target "bba", words ["aab", "aba", "bba", "abb"] 일 때 최소 경로는 aaa -> aba -> bba로 2지만 작성하신 코드는 3을 return 하는 것 같네요.