[level3] 프로그래머스 - 단어 변환(JAVA)

 

 

전체 코드는 맨 밑에 있어요.

 

 

[ 문제 풀이 ]

- 바꿀 수 있는 단어로 모두 바꿔보며 완전탐색한다.

 

 

 

 

[ 풀이 방법 ]

- begin에서 바꿀 수 있는 경우에 대해서 모두 탐색을 해본다.
    => begin과 words[i]의 알파벳 차이가 1개인 경우

 

 

- 알파벳 차이가 1인 단어("hot")가 또 다시 바꿀 수 있는 경우를 찾아 바꾸면서 target인 cog까지 바꿀 수 있는지 확인한다.
   이때, 이미 바꾼 단어로 또 바뀌는 것을 막기 위해 isVisited를 사용한다.
   또, 바꿔진 횟수를 알기 위해 단어를 변경할 때 마다 cnt를 하나씩 증가시킨다.

 

- hot이 바꿀 수있는 단어인 "dot", "lot"으로 차례대로 바꿔본다.
   먼저, dot으로 바꿔보면 다음과 같다.

 

- 이런식으로 방문처리를 하며, 바꿔서 도달할 수 있는 경우의 수를 모두 체크하게 되면
   "hit" -> "hot" -> "dot" -> "dog" -> "cog"까지 오게 된다.

 

 

- 완전탐색을 하다보니, 돌아돌아 "cog"까지 오는 경우도 많겠지만, cnt가 최소인 값을 구하는 것이기 때문에
   현재까지 구한 최솟값을 answer에 저장해두고, 앞으로 구한 cnt와 비교하면 된다.

 

 

 

 

[ 전체 코드 ]

class Solution {
    static boolean isVisited[];
    static int answer = 999999;

    public int solution(String begin, String target, String[] words) {        
        for (int i = 0; i < words.length; i++) {
            if(compare(begin, words[i]) <= 1) {
                isVisited = new boolean[words.length];
                isVisited[i] = true;
                dfs(1, i, target, words);
            }
        }

        return answer == 999999 ? 0 : answer;
    }

    static void dfs(int cnt, int cur, String target, String[] words) {
        if(target.equals(words[cur])) {
            answer = Math.min(cnt, answer);
            return;
        }

        for (int i = 0; i < words.length; i++) {
            if(!isVisited[i] && compare(words[cur], words[i]) == 1) {
                isVisited[i] = true;
                dfs(cnt + 1, i, target, words);
                isVisited[i] = false;
            }
        }
    }

    static int compare(String s1, String s2) {
        int n = 0;
        for (int i = 0; i < s1.length(); i++) 
            if(s1.charAt(i) != s2.charAt(i))
                n++;

        return n;
    }
}

 

 

 

질문이나 코드에 틀린 것이 있다면
댓글 부탁드려요 :)