Lewis's Tech Keep
[프로그래머스] 단어 변환 본문
- dfs/bfs
- 탈출 조건만 잘 잡는다고 생각하면 되었다.
더보기
import java.util.*;
class Solution {
private int min;
private void dfs(String cWord, int stage, String target, String[] words, boolean[] indexArr) {
if(cWord.equals(target)) {
if(min > stage) {
min = stage;
}
return;
}
List<String> nWords = getOneDiffWords(cWord, words, indexArr);
if(nWords.size() == 0) {
return;
}
for(String nWord: nWords ) {
int idx = Arrays.asList(words).indexOf(nWord);
indexArr[idx] = true;
dfs(nWord, stage+1, target, words, indexArr);
}
}
private List<String> getOneDiffWords(String cWord, String[] words, boolean[] indexArr) {
List<String> nWords = new ArrayList<>();
for(int i=0; i<words.length; i++) {
if(indexArr[i]) {
continue;
}
String nWord = words[i];
int count = 0;
for(int j=0; j<nWord.length(); j++) {
if(cWord.charAt(j) != nWord.charAt(j)) {
count++;
}
}
if(count == 1) {
nWords.add(nWord);
}
}
return nWords;
}
public int solution(String begin, String target, String[] words) {
this.min = words.length + 1;
boolean[] indexArr = new boolean[words.length];
dfs(begin, 0, target, words, indexArr);
return min == words.length + 1 ? 0 : min;
}
}
'Java > 알고리즘' 카테고리의 다른 글
[프로그래머스] 2xn 타일링 (0) | 2021.02.23 |
---|---|
[프로그래머스] 게임 맵 최단거리 (0) | 2021.02.18 |
[프로그래머스] 네트워크 (0) | 2021.02.16 |
[TODO][JAVA] 자바 DOC 많이 읽을 것 (0) | 2021.02.15 |
[프로그래머스] 더 맵게 (0) | 2021.02.14 |
Comments