문제는 DFS/BFS 유형으로 분류되어 있으나, 문제를 읽다보니 그래프로 표현해서 다익스트라를 적용 후 begin->target까지의 경로가 존재하는지로도 해결할 수 있을 것 같아서 두 가지 방법으로 모두 풀어보았다.

BFS 풀이

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        boolean[] isVisited = new boolean[words.length];
        LinkedList<Node> q = new LinkedList();
        q.add(new Node(-1, begin, 0));
        while(!q.isEmpty()) {
            Node curN = q.poll();
            for(int i=0; i<words.length; i++) {
                if(curN.index == i) continue;
                if(!isVisited[i] && isOneDiffer(words[i], curN.w)) {
                    isVisited[i] = true;
                    q.add(new Node(i, words[i], curN.d + 1));
                    if(words[i].equals(target)){
                        return curN.d + 1;
                    }
                }
            }
        }
        return 0;
    }
    
    boolean isOneDiffer(String a, String b) {
        int count = 0;
        for(int i=0; i<a.length(); i++){
            if(a.charAt(i) != b.charAt(i)) count++;
        }
        return count==1 ? true : false;
    }
}

class Node {
    final int index;
    final String w;
    final int d;
    Node(int index, String w, int d){
        this.index = index;
        this.w = w;
        this.d = d;
    }
}

다익스트라 풀이

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        HashMap<String,ArrayList<Node>> graph = new HashMap();
        for(String w:words) {
            ArrayList<Node> arr = new ArrayList();
            for(String other:words){
                if(other.equals(w)) continue;
                if(isOneDiffer(w, other)){
                    arr.add(new Node(other,1));
                }
            }
            graph.put(w, arr);
        }
        
        ArrayList<Node> arr = new ArrayList();
        for(String other:words){
            if(other.equals(begin)) continue;
            if(isOneDiffer(begin, other)){
                arr.add(new Node(other,1));
            }
        }
        graph.put(begin, arr);
        
        HashMap<String, Integer> table = new HashMap();
        PriorityQueue<Node> pq = new PriorityQueue<Node>((n1, n2)->{
            return n1.d-n2.d;
        });
        table.put(begin, 0);
        pq.add(new Node(begin, 0));
        
        while(!pq.isEmpty()) {
            Node curN = pq.poll();
            for(Node next:graph.getOrDefault(curN.w, new ArrayList<Node>())){
                if(table.getOrDefault(next.w,10_0000_0000) > curN.d + next.d){
                    table.put(next.w, curN.d + next.d);
                    pq.add(new Node(next.w,  curN.d + next.d));
                }
            }
        }
        
        answer = table.getOrDefault(target, 0);
        if(answer == 10_0000_0000) {
            answer = 0;
        }
        return answer;
    }
    
    boolean isOneDiffer(String a, String b) {
        int count = 0;
        for(int i=0; i<a.length(); i++){
            if(a.charAt(i) != b.charAt(i)) count++;
        }
        return count==1 ? true : false;
    }
}

class Node {
    final String w;
    final int d;
    Node(String w, int d) {
        this.w = w;
        this.d = d;
    }
}

풀리긴했으나 역시 속도가 더 느리다. 그래도 이런 다양한 풀이법에 도전해보는 것도 의미있는 것 같다.