[PG] 단어 변환 JAVA

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

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

시작문자와 목표문자 String begin, target 과 사용할 수 있는 단어들의 배열 String[] words 가 주어진다.

 

begin을 시작으로 하여 words의 원소들로 적절히 단어를 바꿔가며 target에 도달할 수 있는 최소 변경 수를 반환해야한다.

 

단, 단어 변경은 알파벳이 하나 차이나는 단어로만 변경이 가능하며, target에 도달이 불가한 경우는 0을 반환한다.

 

 

 

풀이 .

import java.util.*;

class Solution {
    int answer = 51;
    boolean[] check = null;

    public boolean isPossible(String from, String to) {
        int cnt = 0, len = from.length();
        for(int i = 0; i < len; i++) {
            if(from.charAt(i) == to.charAt(i)) {
                cnt++;
            }
        }
        return cnt == len - 1 ? true : false;
    }


    public void dfs(int dept, String now, String target, String[] words) {
        if(now.equals(target)) {
            answer = Math.min(answer, dept);
            return;
        }

        for(int i = 0; i < words.length; i++) {
            String next = words[i];
            if(check[i] == false && isPossible(now, next)) {
                check[i] = true;
                dfs(dept + 1, next, target, words);
                check[i] = false;
            }
        }
    }

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

        for(int i = 0; i < words.length; i++) {
            String next = words[i];
            if(check[i] == false && isPossible(begin, words[i])) {
                check[i] = true;
                dfs(1, next, target, words);
                check[i] = false;
            }
        }

        return answer == 51 ? 0 : answer;
    }
}

DFS로 풀었다.

words.length의 최대값이 50이므로 answer의 초기값을 51로 잡았다.