Algorithm
프로그래머스 - DFS - 단어 변환
YoonBing9
2021. 3. 15. 16:12
programmers.co.kr/learn/courses/30/lessons/43163
코딩테스트 연습 - 단어 변환
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수
programmers.co.kr
public class 단어_변환 {
public static void main(String[] args) {
단어_변환 o = new 단어_변환();
System.out.println(o.solution("hit", "cog", new String[]{"hot", "dot", "dog", "lot", "log", "cog"}));
//System.out.println(o.solution("hit", "cog", new String[]{"hot", "dot", "dog", "lot", "log"}));
}
private boolean[] isVisit;
private String[] words;
private String target;
private String begin;
private int min = Integer.MAX_VALUE;
public int solution(String begin, String target, String[] words) {
this.begin = begin;
this.target = target;
this.words = words;
isVisit = new boolean[words.length];
dfs(begin, 0, 0);
if(min == Integer.MAX_VALUE) {
min = 0;
}
return min;
}
private void dfs(String curWord, int index, int count) {
if(curWord.equals(target)) {
if(count < min) {
min = count;
}
}
for(int i=0; i<words.length; i++) {
if(!isVisit[i] && isChangeable(curWord, i)) {
isVisit[i] = true;
dfs(words[i], i, ++count);
isVisit[i] = false;
count--;
}
}
}
private boolean isChangeable(String curWord, int changeableIndex) {
String changeableWord = words[changeableIndex];
int count = 0;
for(int i=0; i<curWord.length(); i++) {
if(curWord.charAt(i) != changeableWord.charAt(i)) {
count++;
}
}
return count == 1;
}
}
알고리즘
- 완전탐색, DFS
- 단어를 기준으로 순회하여 다음 단어로 갈 수 있는지 확인한다(단어중 문자 하나만 다르면 이동할 수 있다)
- DFS를 하며 백트래킹 됐을때, 변경횟수와 방문상태를 원래상태로 돌려놔야한다.