문제#
- 링크로 대체
풀이 및 주저리..
프로그래머스 DFS/BFS의 두번째 문제이다. 어려워보였지만 제약이 워낙많아서 생각한대로 풀어보니 구현할 수 있었다. 중복이 없는 것과 항상 답이 존재하니 변환할 수 있는 경우의 수를 모두 구하고 그 중 가장 빠르게 정답에 도달할 수 있는 경우를 검사해서 문제를 풀어보았다. 아쉬운 점은 단어 변환이 가능한 경우를 검사하는 함수가 조금 마음에 안든다는거..? 조금더 깔끔하게 할 수도 있을 것 같은데..
코드
package programmers.school.day03;
public class WordChange {
private int answer;
public int solution(String begin, String target, String[] words) {
boolean[] wordBool = new boolean[words.length];
answer = 0;
findTarget(begin, target, 0, wordBool, words);
return answer;
}
private int findTarget(String begin, String target, int index, boolean[] wordBool, String[] words) {
if (begin.equals(target)) {
return index;
}
for (int i = 0; i < words.length; i++) {
if (wordBool[i])
continue;
if (isChangeable(begin, words[i])) {
wordBool[i] = true;
int temp = findTarget(words[i], target, index + 1, wordBool, words);
wordBool[i] = false;
if(temp == 0) continue;
if(answer == 0 || answer > temp)
answer = temp;
}
}
return 0;
}
private boolean isChangeable(String str, String str2) {
int num = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) != str2.charAt(i)) {
num++;
if (num == 2) {
return false;
}
}
}
return num != 0;
}
}기억에 남길 것!
- 재귀에 익숙해지자