[프로그래머스] 단어 변환 Java

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

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

 

문제 요약

문자열 begin과 target 그리고 문자열 배열 words가 주어진다. begin에서 한 글자씩 바꿔서 target을 만들어야 한다. begin에서 바꿀 값은 words 배열 내에 존재해야하며, target까지 가장 적게 변환한 횟수를 반환하는 함수를 만들어야 한다.

 

문제 풀이

 다른 방식의 문제 같지만 기본적인 DFS 문제이다. 현재 문자열에서 한 글자 바꿨을 때 같아질 수 있는 문자열은 현재 문자열과 인접하다고 생각하면 된다.

 

 boolean 배열의 visit을 만들고 answer 또한 전역으로 선언했다. 그 후 words에서 begin과 같은 문자열이 있다면 방문 필요할 필요가 없기 때문에 이미 방문처리했고, target과 같은 문자열이 있는지 검사해서 없다면 0을 반환했다.

 

 또한 두 문자열이 인접(한 글자 차이)한지 여부를 반환하는 isChangeable 함수를 만들고, dfs를 이용해서 인접한 words로 하나씩 탐색했다. target에 도달했을 때 depth 값을 answer과 비교해서 더 작다면 answer에 초기화하였다.

 

나의 코드

class 단어_변환 {
    boolean[] visited;
    int answer = 11;

    public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];

        /* words 배열에서 begin, target 있는지 검사 */
        boolean isPossible = false;
        for (int i = 0; i < words.length; ++i) {
            visited[i] = (words[i].equals(begin)) ? true : false; // begin 으로 되돌아 올 필요는 없음
            isPossible = (words[i].equals(target)) ? true : isPossible; // target 이 없으면 안된다.
        }
        if (!isPossible)
            return 0;

        // dfs 이용해서 최소값 반환
        dfs(begin, target, words, 0);
        return (answer == 11) ? 0 : answer;
    }

    /* 재귀를 이용해서 target 을 찾아가는 dfs 함수 */
    public void dfs(String now, String target, String[] words, int depth) {
        // target 에 도달 했을 때
        if (now.equals(target))
            answer = (answer > depth) ? depth : answer;

        for (int i = 0; i < words.length; ++i) {
            if (!visited[i] && isChangeable(now, words[i])) {
                visited[i] = true;
                dfs(words[i], target, words, depth + 1);
                visited[i] = false;
            }
        }
    }

    /* 두 문자열이 인접한지 반환하는 함수 (알파벳 하나 차이인지) */
    public boolean isChangeable(String s1, String s2) {
        int count = 0;
        for (int i = 0; i < s1.length(); ++i) {
            if (s1.charAt(i) != s2.charAt(i))
                count++;
        }

        return (count == 1) ? true : false;
    }
}