[javascript] 프로그래머스 단어 변환 (DFS/BFS)

문제

두 개의 단어 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 합니다.

풀이

(*저도 공부하면서 쓴 거라 오류가 있다면 너그러이 댓글 부탁드려요…)

한 번에 한 개의 알파벳이 바뀐 단어를 각각의 노드로 생각하면 아래와 같은 형태로 트리 구조를 만들 수 있다.

위와 같은 구조를 BFS(너비우선탐색) 방식과 DFS(깊이우선탐색)방식으로 구분해 풀어보았다.

BFS(너비우선탐색)

BFS 방식은 동일한 레벨에 존재하는 노드를 모두 방문한 뒤 다음 레벨으로 탐색을 이어가는 방법이다. 노드 탐색의 순서가 아래와 같이 진행된다.

BFS는 queue 형태의 자료구조를 이용해 아래와 같이 탐색을 진행한다.

1. 각 노드와 동일한 레벨에 존재하는 노드를 queue에 추가(push)하고
2. 제일 먼저 추가된 노드를 꺼내고 (shift)
3. 꺼낸 노드의 다음 레벨에 존재하는 노드들을 다시 queue에 추가(push) 하는 과정을 반복한다.

단어 변환 문제에 BFS를 적용하면 아래와 같이 진행된다.

1. begin을 먼저 queue에 추가한다.
2. begin의 글자들을 순회하며 words 배열 내 begin과 한 개의 알파벳만 다른 단어들을 queue에 추가한다.
3. queue에서 제일 먼저 추가된 단어를 꺼내고, 현재 단어가 target과 일치하는지 확인한다. 1) 일치한다면, 현재의 레벨을 반환하고, 2) 일치하지 않는다면, 현재 단어와 words 배열 내 한 개의 알파벳만 다른 단어들(다음 레벨에 연결된 단어들이다.)을 임시 배열 temp에 추가한다.
4. queue가 비었다면 현재 레벨에 가능한 단어는 모두 탐색했다는 의미이다. 임시 배열 temp에 추가했던 단어들을 다시 queue에 추가함으로써 다음 레벨로 탐색을 이어간다.

위 과정의 반복을 통해 문제를 풀 수 있다.

단, 이미 탐색한 단어를 다시 queue에 추가한다면 hot -> dot -> hot -> dot …과 같이 무한 루프가 반복된다. 이미 탐색한 단어는 visited 배열에 추가하여 queue에 동일한 단어가 추가되지 않도록 하는 단계가 필요하다.

소스코드는 아래와 같다.

DFS(깊이우선탐색)

재귀를 이용하여 하나의 노드에서 이어지는 레벨에 깊게 파고드는 방법으로 문제를 풀어 보았다. 현재 단어와 한 알파벳만 다른 단어들을 깊게 탐색해 target과 동일한 단어가 나올 때까지의 레벨을 모두 계산하고, 이 중 가장 작은 수를 반환하면 된다. 모든 경우의 수를 확인하므로 시간 복잡도나 공간 복잡도 측면에서 BFS보다 훨씬 더 비효율적인 것 같다.

DFS로 표현되는 트리와 순서는 아래와 같다.

단어 변환 문제에 DFS를 적용하면 아래와 같이 진행된다.

1. 현재 단어와 한 알파벳만 다른 다음 레벨의 단어들을 임시 배열 temp 에 추가한다.
2. temp 배열을 순회하며 각각의 단어에서 다음 레벨의 단어들을 탐색하는 함수를 재귀적으로 실행한다. 배열 값 하나마다 재귀 함수가 실행되므로 배열의 한 값과 관련된 레벨을 모두 탐색한 뒤 다음 값의 탐색이 이어진다.
3. 만약 현재 값이 target과 동일하다면 현재의 레벨을 answers 배열에 추가한 뒤 재귀함수를 종료한다.

begin의 글자를 모두 탐색할 때가지 위 과정을 반복한 후, answers 배열에서 가장 작은 값을 반환해주면 된다.

이미 탐색한 단어를 저장하는 방법에서도 BFS과 DFS는 큰 차이가 있다.

BFS에서는 하나의 visited 배열을 생성해두고 모든 레벨의 단어를 탐색할 때 동일한 visited 배열에 해당 단어가 존재하는지 확인하면 됐다.

그러나 DFS에서는 재귀함수를 호출할 때마다 새로운 visited 배열을 생성해야 한다. 배열 temp를 순회할 때, 현재의 단어만 포함하는 새로운 visited 배열을 생성하고 이를 해당 단어의 다음 레벨에 전달한다. 다음 레벨에서는 전달받은 visited 배열에 다음 레벨의 해당 단어만 포함하는 새로운 visited 배열을 생성하고, 이를 또 다음 레벨로 전달해줘야 한다. 즉, 동일한 레벨에 존재하는 모든 단어들, 배열 temp의 모든 값을 아직 탐색하지도 않았는데도 visited 배열에 추가하면 안 된다는 것이다.

소스코드는 아래와 같다.

어렵고만