오늘도 재밌게 푼 문제 ! ( 너무 어렵지도 쉽지도 않아서 적당히 고민해서 재밌게 풀 수 있는 문제인 것 같은 )
그래서 오늘 푼 문제는 프로그래머스 고득점 kit DFS/BFS 분류에 있는 Level3 문제이다 !
https://programmers.co.kr/learn/courses/30/lessons/43163
문제 설명
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
- 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
- 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 |
풀이 방법
begin과 words에 있는 각 단어를 노드라고 생각하고, 당연하게도 begin을 시작 노드로 두고 탐색을 진행하면 된다. 이 때, 각 노드의 연결은 한 번에 한 개의 알파벳만 바꿀 수 있다고 했기 때문에 한 개의 알파벳을 바꾸어서 갈 수 있는 단어들끼리 연결되었다고 생각하고 문제 풀이를 진행하였다. 입출력 예 첫번째를 그래프로 그려보면 아래의 그림과 같다.
hit부터 target인 cog까지 BFS 탐색을 통해서 depth를 구해서 반환해주면 된다.
이것을 코드로 구현하는 과정에서 따로 특정 자료구조를 이용해서 graph를 만들지는 않았다. 다만 현 노드에서 연결된 노드를 구할 수 있도록 하나의 알파벳만 변경해서 만들 수 있는지 체크하는 함수를 만들어 사용하였다. 또한 이미 방문한 노드는 재방문하지 않기 위해 visited를 사용하였다. 또한 BFS탐색을 위해서 사용하는 Queue를 2개 두어 깊은 복사를 통해서 같은 depth 라인에 대해서 탐색을 완료하고 다음 depth의 탐색을 진행할 수 있도록, 그 depth를 구분할 수 있도록 해주었다.
또한 target에 도달할 수 없는 경우인, words에 target이 포함되지 않거나, begin부터 target까지 경로가 존재하지 않는 경우에는 0을 반환해야 하는데, 후자의 경우는 탐색을 통해서 알아가야 하지만 전자는 그게 아닌데도 탐색을 끝까지 진행해야 알 수 있게되는 비효율성을 피하기 위해 처음에 words에 target이 포함되어 있는지 확인하는 과정을 추가해주었다 !
코드
import java.util.*;
public class Solution {
public static boolean isNear(String str1, String str2){
boolean diff = false;
for (int i=0; i<str1.length(); i++){
if (str1.charAt(i) != str2.charAt(i)){
if(diff) return false;
else diff = true;
}
}
return diff;
}
public static int solution(String begin, String target, String[] words) {
int answer = 0;
boolean isContain = false;
for (String word : words) {
if (word.equals(target)) {
isContain = true;
break;
}
}
if(!isContain) return 0;
boolean[] visited = new boolean[words.length];
Arrays.fill(visited, false);
Queue<String> currentQueue = new LinkedList<>();
Queue<String> nextQueue = new LinkedList<>();
nextQueue.add(begin);
String current;
while(!nextQueue.isEmpty()){
currentQueue.addAll(nextQueue);
nextQueue.clear();
answer++;
while(!currentQueue.isEmpty()){
current = currentQueue.poll();
if(current.equals(target)) return answer-1;
for(int i=0; i<words.length; i++){
if(isNear(current, words[i]) && !visited[i]){
nextQueue.add(words[i]);
visited[i] = true;
}
}
}
}
return 0;
}
}