[스위프트 알고리즘] 프로그래머스: 단어 변환

문제

https://programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. 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 합니다.

풀이

처음 문제를 보고 "와 어렵다고"라고 생각했는데, 한번에 하나의 알파벳만 바꿀 수 있고, words에 있는 단어로만 변환할 수 있다는 조건때문에 간단한 문제로 바뀌었습니다. 최소 단계를 알아내야하기 때문에 DFS로 풀지 않고 BFS로 풀었습니다.

 

depth를 저장하는 여러가지 방법들이 있지만, 저는 depth가 시작할 때 큐의 크기를 미리 저장해두고 해당 크기만큼 반복문을 돌면 depth를 올려주는 방식을 주로 사용하고 있습니다. for 문이 하나 더 생겨서 코드는 좀 못생겼지만 depth에 대한 모델 데이터를 따로 관리하지 않아도 돼서 편하더라구요.

 

문제 해결을 위한 알고리즘은 words 배열에서 단어를 하나씩 꺼내서 현재 기준이 되는 단어에서 한글자만 바꿔서 만들 수 있는 단어라면 큐에 삽입해주는 방식으로 구현했습니다. 매 반복마다 큐에서 단어를 꺼내서 사용하고,  새로 꺼낸 단어가 target으로 지정한 단어와 같은 단어이면 종료하고 depth를 반환하도록 헀습니다.

 

추가적으로 연산시간을 최대한 줄이기 위해서 이미 검사했던 단어를 Set에 저장해두어서 검사하지 않은 새로운 단어만 검사하도록 하고, BFS에서는 주로 큐를 사용하지만 이 경우에는 depth만 구해주면 되기 때문에 배열의 마지막에 계속 append를 하고 새로운 단어를 꺼낼 때는 뒤에서부터 꺼내서 큐(처럼 사용하는 배열)의 삽입과 삭제가 O(1)이 보장되도록 했습니다.

코드