[Programmers] LV3 - 단어 변환

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

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

 

 

 

문제 파악

 

문제에 나와 있듯이

1. 한 번에 한 개의 알파벳만 변환할 수 있다.

2. words 배열에 있는 단어로만 변환할 수 있다.

3. begin에서 target으로의 변환 할 때까지 걸린 횟수를 return 하고, 변환할 수 없을 경우 0을 return 해준다.

 

import java.util.*;
class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = 0;

        boolean[] visited = new boolean[words.length];
        Queue<String> q = new LinkedList<>();

        q.add(begin);

        answer = dfs(q, visited, words, target, 0);

        return answer;
    }

    public int dfs(Queue<String> q, boolean[] visited, String[] words, String target, int depth)
    {
        int result = Integer.MAX_VALUE;
        while (!q.isEmpty())
        {
            int size = q.size();
            for (int sz = 0; sz < size; sz++) {
                String str = q.poll();
                if (str.equals(target)) {
                    return Math.min(result, depth);
                }

                char[] origin = str.toCharArray();
                for (int i = 0; i < words.length; i++) {
                    int cnt = 0;
                    char[] change = words[i].toCharArray();
                    for (int j = 0; j < change.length; j++) {
                        if (origin[j] != change[j]) {
                            cnt++;
                        }
                    }
                    if (cnt == 1 && !visited[i]) {
                        visited[i] = true;
                        q.add(words[i]);
                    }
                }
            }
            depth++;
        }
        return 0;
    }
}