이번에 푼 문제는 프로그래머스의 단어변환 문제이다.
문제
문제 설명
두 개의 단어 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 |
예제 설명
이 문제는 BFS로 푸는게 더 효율적인 문제이다.
먼저 예제를 분석하면서 문제의 요구사항에 대해 설명하겠다.
EX 1:
begin : hit
target: cog
words: ["hot", "dot", "dog", "lot", "log", "cog"]문제에서 words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환한다고 설명한다.
우리는 이 문제를 BFS로 풀 것인데, 그 이유에 대해 DFS와 BFS를 비교하며 설명하겠다.
문제 풀이
나는 해당 문제를 BFS로 풀었다. 그 이유는 hit과 cog 사이의 최단 경로를 구하는 문제이기 때문이다.
1. BFS 그래프
BFS의 경우 위의 사진의 화살표 순서로 탐색한다.
사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택과정: BFS는 인접한 노드들을 전부 탐색한다음, 이 노드들에 인접한 방문하지 않은 노드들을 모두 방문예제: hit과 인접한 hot, lot을 방문한 다음, 이 노드들에 인접하고 방문하지 않은 dot, log를 방문
문제에서 hit에서 cog로 변환하는 최단 경로를 구하는 것을 목표로 하므로 BFS가 효율적이다.
2. DFS 그래프
반면 DFS의 경우 위의 사진처럼 모든 경로를 탐색한다음 그 중 최단 경로를 구한다.
사용하는 경우: 1) 모든 노드를 탐색하거나 2) 한 쪽 경로를 깊게 파야하는 경우 사용예제: hit → cog로 변환하는 경로가-
hot → dot → dog → cog (4)
-
hot → dot → lot → log → cog (5)
이며 이 중 최단 경로인 “hot → dot → dog → cog (4)”를 리턴
-
Pseudocode
cnt <- 0
큐 = []
if (target이 words에 없으면) return;
[begin, cnt]를 큐에 넣고 추가함 표시
while (큐가 비어있지 않다면)
w <- 큐에서 가장 앞에 있는 노드
w를 큐에서 빼주고 방문함 표시
if (w가 target과 같다면) return cnt;
for u ∈ N
if (u가 방문한 노드면) return;
if (u와 w가 한 글자 차이) then
큐에 [u, ++cnt]를 추가하고 추가함 표시전체 코드
function solution(begin, target, words) {
let answer = 0;
let visit = [];
let queue = [];
if(!words.includes(target)) return 0;
queue.push([begin,answer]);
while(queue) {
let [v, cnt] = queue.shift();
if (v === target) {
return cnt;
}
words.forEach(word => {
let notEqual = 0;
if (visit.includes(word)) return;
for (let i = 0; i < word.length; i++) {
if (word[i] !== v[i]) {
notEqual++;
}
}
if (notEqual === 1) {
queue.push([word, ++cnt]);
visit.push(word);
}
});
}
}