이 문제의 목표는 시작 단어인 begin에서 목표 단어인 target으로 변환하는 최소 단계를 구하는 것이다. 변환 규칙은 한 번에 한 글자만 변경할 수 있고, 변경 후의 단어는 반드시 주어진 단어 집합 words 안에 존재해야 한다. 문제를 해결하기 위해 먼저 모든 단어를 그래프의 노드로 생각할 수 있다. 두 노드는 두 단어가 단 하나의 알파벳만 다를 때 서로 연결되어 있다고 가정하면, 이 문제는 begin에서 target까지의 최단 경로를 찾는 문제로 전환된다.
최단 경로를 구하기 위해 너비 우선 탐색(BFS)를 사용한다. BFS는 가중치가 없는 그래프에서 시작 노드로부터 각 노드까지의 최단 거리를 보장하는 탐색 방법이기 때문에, 첫 번째로 target에 도달하는 순간 그것이 최소 단계가 된다. 알고리즘의 첫 단계에서는 target이 words 목록에 존재하는지 확인한다. 만약 존재하지 않는다면 변환이 불가능한 것으로 간주하여 0을 반환한다. 그 후, 시작 단어인 begin과 초기 단계 0을 큐에 넣고 BFS를 시작한다. 큐에서 단어와 그 단어까지 도달한 단계 수를 꺼내고, 해당 단어가 target과 같으면 지금까지의 단계 수를 결과로 반한다. 만약 그렇지 않다면, 현재 단어와 한 글자만 다른 단어들을 words 집합에서 찾아 아직 방문하지 않은 단어들을 큐에 추가하면서 단계 수를 1씩 증가시킨다. 이 과정에서 한 번 방문한 단어는 다시 방문하지 않도록 관리하여 중복 탐색을 방지한다.
이와 같이 BFS 방식으로 탐색을 진행하면, begin에서 target으로 변환하는 가장 짧은 경로, 즉 최소 변환 단계를 효율적으로 구할 수 있으며, target으로의 변환이 불가능한 경우에는 0을 반환하게 된다.
import java.util.LinkedList;
import java.util.Queue;
public class WordConversionBreadth {
private static class WordNode {
String word;
int steps;
WordNode(String word, int steps) {
this.word = word;
this.steps = steps;
}
}
public int solution(String begin, String target, String[] words) {
boolean targetExists = false;
for (int i = 0; i < words.length; i++) if (words[i].equals(target)) targetExists = true;
if (!targetExists) return 0;
boolean[] visited = new boolean[words.length];
Queue<WordNode> queue = new LinkedList<>();
queue.add(new WordNode(begin, 0));
while (!queue.isEmpty()) {
WordNode current = queue.poll();
if (current.word.equals(target)) return current.steps;
for (int i = 0; i < words.length; i++) {
if (!visited[i] && isOnlyOneAlphabetDifferent(current.word, words[i])) {
visited[i] = true;
queue.add(new WordNode(words[i], current.steps + 1));
}
}
}
return 0;
}
public static boolean isOnlyOneAlphabetDifferent(String str1, String str2) {
int diffCount = 0;
for (int i = 0; i < str1.length(); i++) {
if (str1.charAt(i) != str2.charAt(i)) {
diffCount++;
if (diffCount > 1) return false;
}
}
return diffCount == 1;
}
}