문제
두 개의 단어 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 합니다.
입출력 예시
| begin | target | words | return |
|---|---|---|---|
| "hit" | "cog" | ["hot", "dot", "dog", "lot", "log", "cog"] | 4 |
| "hit" | "cog" | ["hot", "dot", "dog", "lot", "log"] | 0 |
풀이
해당 문제는 카테고리가 DFS/BFS 로 분류가 되어있으니 두 개의 탐색 알고리즘 중 하나를 택해 구현할 수 있을 것이다. 아직 DFS와 BFS가 어떤 알고리즘인지 모른다면 먼저 해당 개념을 숙지하고 풀이하는 것을 추천한다.
문제를 언뜻 보아서는 그래프의 형태가 아닌데 DFS 또는 BFS를 적용할 수 있는지에 대한 의문이 들 수 있다. 노드가 몇개 있고, 각 노드들의 연결 관계는 이러이러하다라는 사전 정보가 없기에 그렇게 생각할 수 있다. 만약 해당 문제가 DFS/BFS 라는 카테고리로 주어지지 않았다면 그 의문은 더욱 클 수 있을 것 이다.
그러나 문제에서 주어진 words배열의 각 원소를 우리는 각각의 Node로 인식해보자. 이들의 연결 관계(= 간선의 정보)는 물론 주어지지 않았다. 그러나 문제의 조건을 보게되면 각각의 노드는 어떤 특정 순서로 방문을 할 수 있다. 그 조건은 다음과 같다.
현재 문자열의 노드와 단 하나의 철자만 다른 문자열을 가진 노드
따라서 해당 조건이 두 노드 사이의 연결 조건으로 성립한다. 만약 해당 조건이 참인 경우에 두 노드는 연결이 되었다고 판단할 수 있는 것이다. 따라서 먼저 두 노드의 연결 여부를 판단할 수 있는 체크함수를 다음과 같이 구현했다.
const isConnected = (str1, str2) => {
let count = 0;
const len = str1.length;
// 문제 조건에 의해 두 문자열의 길이는 항상 동일하다.
// 반복문을 돌며 서로 다른 철자가 2개 이상이 되면 거짓
// 서로 다른 철자가 딱 1개라면 참을 반환한다.
for(let i = 0; i < len; i++) {
if(str1[i] !== str2[i]) count++;
}
// 반복문에서 if(count > 1) return false;
// 와 같이 빠르게 끝내도 되지 않는가 할 수 있는데,
// count가 0인 경우(== 단어자체가 모두 다른경우)를 잡아내지 못한다.
// 때문에 그냥 반복문을 다 돌고 count가 정확하게 1인 경우만 true를 반환
return count === 1 ? true : false;
}다음은 DFS 또는 BFS를 통해 주어진 words를 노드 삼아 탐색하면 되겠다. 해당 문제에서는 BFS를 이용하여 풀이해보겠다.
기본적으로 DFS가 유리한 환경과 BFS가 유리한 환경이 있다. 관련해서는 다른 포스팅을 찾아보는 것을 추천한다. 해당 문제에서는 그러한 이점은 고려하지 않고 그냥 BFS를 선택했다. 개인적으로 JS에서는 꼭 DFS 로직이 필요하거나 DFS로 구현하는 것이 더 간편한 경우가 아니라면 DFS를 선호하지 않는다. Lv.4-5 단계에서 다른 언어 처럼 JS에서 DFS를 구현하면 유독 stack overflow가 많이 터진다... 관련해서는 해당 레벨의 문제들을 다룰 때 더 자세히 이야기 해보자!
BFS 알고리즘의 특성상 연결된 노드들을 우선 방문하고 다음 deps로 넘어가게 된다. 여기서 연결된 노드들은 우리가 앞서 만들어준 check 함수에 의해 서로 철자가 딱 하나만 다른 노드(= 문자열)를 의미한다.
우리가 구해야 하는 것은 begin에서 시작하여 target까지 몇번만에 도달할 수 있는지이다. 역시 BFS의 특성상 현재 단계에서 방문하고 있는 노드들의 deps는 이전 단계의 deps + 1과 같다. 즉 visited 라는 방문여부를 체크할 변수를 만들어주고, begin에서 시작하는 문자열을 0 부터 시작하여 BFS 탐색을 하며 deps + 1을 통해 각 문자열의 visited 레벨을 관리해주면 target 문자열에 몇 번만에 도달했는지 쉽게 파악할 수 있다. 이를 구현하면 아래와 같다.
const visited = {}; // 방문여부를 저장할 변수 선언
const queue = []; // BFS를 돌기 위한 queue 선언
// 첫 시작 노드로 queue와 visited를 초기화한다
// 또는 아래 전체코드에서처럼 선언과 동시에 초기화해줄 수도 있다
queue.push(begin);
visited[begin] = 0;
// BFS 탐색 시작
while(queue.length) {
const cur = queue.shift();
// target과 일치한 경우 반복을 종료한다.
if(cur === target) break;
for(const word of words) {
if(isConnected(cur, word) && !visited[word]) {
// 이 부분이 핵심이다. 연결은 되어있지만 아직 방문하지 않은 경우라면,
// 방문여부를 활성화하는데 이때 현재 deps 값을 넣어준다.
// 위에서 설명했듯 현재 deps는 이전 deps + 1 이다.
visited[word] = visited[cur] + 1;
queue.push(word);
}
}
}이때 문제에 조건에 의해 항상 target 단어가 존재하지 않는다는 것을 알 수 있고, 이 경우에는 0을 리턴하라는 것을 알 수 있다. 따라서 다음과 같이 리턴을 선언해주자.
return visited[target] ? visited[target] : 0;주석을 제외한 전체코드는 아래와 같다.
코드
function solution(begin, target, words) {
const visited = { [begin] : 0 };
const queue = [begin];
while(queue.length) {
const cur = queue.shift();
if(cur === target) break;
for(const word of words) {
if(isConnected(word, cur) && !visited[word]) {
visited[word] = visited[cur] + 1;
queue.push(word);
}
}
}
return visited[target] ? visited[target] : 0;
}
const isConnected = (str1, str2) => {
let count = 0;
const len = str1.length;
for(let i = 0; i < len; i++) {
if(str1[i] !== str2[i]) count++;
}
return count === 1 ? true : false;
}출처
