|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
import java.util.*;
class Solution {
private static int min;
public static void DFS(ArrayList<String> wordList, String str, String target, int n, int cnt) {
// 변환 최솟값 저장
if (str.equals(target)) {
if (min > cnt)
min = cnt;
return;
}
for (int i = 0; i < n; i++) {
// 변환 가능할 시에만 수행
if (isConvertible(str, wordList.get(i))) {
// 변환 가능한 모든 경로 탐색
String s = wordList.remove(i);
DFS(wordList, s, target, n - 1, cnt + 1);
wordList.add(i, s);
}
}
}
public static boolean isConvertible(String s1, String s2) {
int chk = 0;
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) != s2.charAt(i))
chk++;
if (chk > 1)
return false;
}
return true;
}
public int solution(String begin, String target, String[] words) {
int answer = 0;
ArrayList<String> wordList = new ArrayList<String>();
min = words.length;
for (int i = 0; i < words.length; i++)
wordList.add(words[i]);
// target이 없는 경우
if (!wordList.contains(target)) {
return 0;
}
DFS(wordList, begin, target, words.length, 0);
answer = min;
return answer;
}
}
|
cs |
ArrayList를 이용한 모든 경우의 수를 얻어내는 코드를 조금 변형하였다.
사용할 수 있는 목록이 저장된 ArrayList 하나만 사용하였고, 현재 상태는 단순히 String으로 저장하였다.