정답(Solution)
1. 재귀를 사용한 풀이
import java.util.*;
class Solution {
private List<Integer> iList = new ArrayList<>();
public int solution(String begin, String target, String[] words) {
boolean f = false;
for(String str : words){
if(target.equals(str)){
f = true;
break;
}
}
if(f){
boolean[] v = new boolean[words.length];
dfs(begin, target, words, v, 0);
}else{
return 0;
}
int[] a =iList.stream().sorted().limit(1).mapToInt(Integer::intValue).toArray();
return a[0];
}
private void dfs(String begin, String target, String[] words, boolean[] v, int sum){
if(begin.equals(target)){
iList.add(sum);
return;
}
for(int i=0; i<words.length; i++){
if(!v[i] && check(begin, words[i])){
v[i] = true;
dfs(words[i], target, words, v, sum + 1);
v[i] = false;
}
}
}
private boolean check(String begin, String word){
char[] a = begin.toCharArray();
char[] b = word.toCharArray();
int cnt = 0;
for(int i=0; i<a.length; i++){
if(a[i] != b[i]){
cnt++;
}
}
return cnt == 1 ? true : false;
}
}
분석
- dfs문제이다.
- 변환시킬 수 있는 단어인지 체크하는 함수와 방문 여부를 체크하는 배열 v만 잘 정리해주면 된다.
2. Stack을 사용한 풀이
import java.util.*;
class Solution {
public int solution(String begin, String target, String[] words) {
int answer = 0;
Arrays.sort(words);
int num = Arrays.binarySearch(words, target);
int len = words.length;
if(num >= 0){
Stack<String> stk = new Stack<>();
stk.push(begin);
boolean[] v = new boolean[len];
while(!stk.isEmpty()){
String str = stk.pop();
for(int i=0; i<len; i++){
if(v[i]) continue;
if(target.equals(str)) return answer;
if(check(words[i], str)){
v[i] = true;
stk.push(words[i]);
answer++;
break;
}
}
}
return answer;
}else{
return 0;
}
}
private boolean check(String str1, String str2){
int count = 0;
for(int i=0; i<str1.length(); i++){
if(str1.charAt(i) != str2.charAt(i)){
count++;
}
}
return count == 1 ? true : false;
}
}
분석
- Stack을 활용하여 dfs방식으로 풀이하였다.
- 1개의 char만 다른지 확인하는 check 함수를 만들어서 변환 가능한지 체크하였다.