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

[문제링크 - 프로그래머스 - 단어 변환] https://school.programmers.co.kr/learn/courses/30/lessons/43163

소스 코드1 (BFS)

• 빠른 횟수를 구하기 때문에 BFS가 떠올랐다.
• 문제를 읽고 노트에 조건에 대해 적으면서 생각한 후, 코드로 옮겼는데 바로 성공!
• 성장한 거 같아서 뿌듯했다😆

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        boolean[] visit = new boolean[words.length];
        Queue<String> queue = new LinkedList<>();
        queue.offer(begin);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0; i<size; i++){
                String str = queue.poll();
                if(str.equals(target))
                    return answer;
                for(int j=0; j<words.length; j++) {
                    if(!visit[j] && canConvert(str, words[j])){
                        visit[j] = true;
                        queue.offer(words[j]);
                    }
                }
            }
            answer++;
        }
        return 0;
    }

    boolean canConvert(String str1, String str2){
        int cnt = 0;
        for(int i=0; i<str1.length(); i++){
            if(str1.charAt(i) != str2.charAt(i)){
                cnt++;
                if(cnt > 1) return false;
            }
        }
        if(cnt == 1){
            return true;
        }
        else return false;
    }
}

소스 코드2 (DFS)

• DFS로도 풀 수 있을 것 같아 공부하는 겸 한 번 풀어봤다.

class Solution1 {
    static int answer = Integer.MAX_VALUE;
    static boolean[] visit;
    public int solution(String begin, String target, String[] words) {
        visit = new boolean[words.length];
        dfs(0, begin, target, words);
        return answer == Integer.MAX_VALUE ? 0 : answer;
    }

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

        for(int i=0; i<words.length; i++) {
            if (!visit[i] && canConvert(word, words[i])) {
                visit[i] = true;
                dfs(n + 1, words[i], target, words);
                visit[i] = false;
            }
        }
    }

    boolean canConvert(String str1, String str2){
        int cnt = 0;
        for(int i=0; i<str1.length(); i++){
            if(str1.charAt(i) != str2.charAt(i)){
                cnt++;
                if(cnt > 1) return false;
            }
        }
        if(cnt == 1){
            return true;
        }
        else return false;
    }
}