프로그래머스 단어변환 자바 풀이

https://programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환

프로그래머스 여행 경로와 거의 비슷한 문제다.

단어의 1글자만 다른 것을 찾아서 DFS로 풀면 된다.

1글자를 찾기 위해서 처음엔 begin, target는 1차원 배열로 words는 2차원 배열로 변경하려 했으나 간단한 방법이 있음을 깨닫고 charAt 함수를 이용해 비교했다.

주석 처리 해둔 부분은 처음에 return 을 위해 필요한 조건이라 생각했으나, cnt가 words의 길이만큼 같아졌다는 뜻은 words 배열의 모든 단어를 체크했다는 뜻이니 그렇다면 for문이 끝나 알아서 한 뎁스가 완료 될 것이다. 그러므로 필요 없는 코드다.

 

다른 블로그를 참조하니 charAt 함수를 이용해 바로 == 으로 비교를 했던데 나는 그렇게 하면 tc 통과가 되지 않았다. 왜인지 알게되면 추가로 적어 놔야겠다.

import java.util.Arrays;

public class ChangeWords {

    boolean[] visit;
    int answer = 51;

    public int solution(String begin, String target, String[] words) {

        int WordsSize = words.length;
        visit = new boolean[WordsSize];

        if(!Arrays.asList(words).contains(target)) answer = 0;
        else DFS(begin, target, words, 0);

        return answer;
    }

    private void DFS(String begin, String target, String[] word, int cnt) {

        if(begin.equals(target)) {
            if(answer > cnt) answer = cnt;
            return;
        }
	//else if (cnt == word.length) return;

        for(int i = 0; i < word.length; i ++) {
            int dif = 0;
            for(int j = 0; j < begin.length(); j ++) {
                if(!String.valueOf(word[i].charAt(j)).equals(String.valueOf(begin.charAt(j)))) {
                   dif ++;
                }
            }
            if(dif == 1 && !visit[i]) {
                visit[i] = true;
                DFS(word[i], target, word, cnt + 1);
                visit[i] = false;
            }
        }
    }
}