[Programmers] 단어 변환

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

[DFS + 백트래킹]

시작 단어에서 목표 단어까지 최소 몇번의 변환을 거쳐 도달할 수 있는지에 대한 문제이다. 주어진 단어 배열의 각 원소를 하나의 정점(V)로 보고, 방문했는지에 대한 체크 값을 잘 사용하면 어렵지 않게 풀 수 있다.

 

코드가 그리 복잡하지 않고 주석이 있으므로 함께 보면 더 이해가 빠를 것 같다.

Code </>

package org.gorany.programmers.단어변환;

class Solution {

    static final int INF = 1000000000;
    static int size; //단어 몇개?
    static int wordLength; //단어 길이?
    static int min = INF;
    static boolean[] check = new boolean[50];

    /*
    * origin -> other로 바꿀 수 있는지 체크하는 메서드
    * false : 변환 X
    * true : 변환 O
    * */
    static boolean canTransform(String origin, String other){
        char[] org = origin.toCharArray();
        char[] ot = other.toCharArray();

        int differ = 0;
        for(int i=0; i<wordLength; i++)
            if(org[i] != ot[i])
                differ++;

        return differ < 2;
    }
    /*
    * 단어를 변환할 수 있는지 탐색하는 메서드
    * cur : 현재 단어
    * target : 목표 단어
    * words : 주어진 단어들
    * curIdx : 현재 단어의 index (-1 = 처음 시작할 때)
    * count : 단어를 몇 번 바꿨는지
    * */
    static void DFS(String cur, String target, String[] words, int curIdx, int count){

        if(cur.equals(target)){
            min = Math.min(min, count);
            return;
        }

        if(curIdx != -1) check[curIdx] = true;

        for(int i=0; i<size; i++){
            if(check[i]) continue;

            if(canTransform(cur, words[i]))
                DFS(words[i], target, words, i, count + 1);
        }

        if(curIdx != -1) check[curIdx] = false;
    }

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

        //init
        size = words.length;
        wordLength = words[0].length();
        //search
        DFS(begin, target, words, -1, 0);

        return min == INF? 0 : min;
    }
}

class Main{
    public static void main(String[] args) {
        Solution sol = new Solution();

        String s = "hit";
        String e = "cog";
        String[] ws = {"hot", "dot", "dog", "lot", "log", "cog"};

        System.out.println(sol.solution(s, e, ws));
    }
}