두 개의 단어 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 함수를 작성해주세요.
begin | target | words | return |
---|---|---|---|
"hit" | "cog" | ["hot", "dot", "dog", "lot", "log", "cog"] | 4 |
"hit" | "cog" | ["hot", "dot", "dog", "lot", "log"] | 0 |
예제 #1
문제에 나온 예와 같습니다.
예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.
넓이 우선 탐색을 사용하자
Pair
라는 클래스를 만들자Queue
를 만들어서 new pair(과정의수 : 0, 시작 단어 : begin)
을 넣습니다.queue
에서 데이터를 뽑고 str
와 한 문자가 다른 문자열을 words
에서 찾아 다시 queue
에 넣습니다target
문자열을 찾습니다.없을 경우를 처리할때
cnt
가 words
의 개수보다 커지면 모든 경우를 다 둘러보았기 때문에 없다고 판단하면 됩니다.
아래와 같은 if문으로 처리해줍니다.
if (cur.str.equals(target)) {
answer = cur.cnt;
break;
}
코드
import java.util.*;
class Solution {
public int solution(String begin, String target, String[] words) {
int answer = 100;
Queue<Pair> queue = new LinkedList<>();
queue.offer(new Pair(0, begin));
int len = words.length;
Pair cur;
while (!queue.isEmpty()) {
cur = queue.poll();
if (cur.str.equals(target)) {
answer = cur.cnt;
break;
}
if (cur.cnt > len){
continue;
}
for (String word : words) {
int cnt = 0;
for (int i = 0 ; i < begin.length() ; i++){
if (word.charAt(i) != cur.str.charAt(i)) {
cnt++;
}
}
if (cnt == 1){
queue.offer(new Pair(cur.cnt + 1, word));
}
}
}
return answer == 100 ? 0 : answer;
}
}
class Pair{
int cnt;
String str;
public Pair(int cnt, String str) {
this.cnt = cnt;
this.str = str;
}
}