문제

풀이

words에 target이 없다면 0을 반환한다.

begin부터 words에서 해당하는 값과 하나의 글자만 차이가 나는 단어를 찾는다.
해당하는 단어들을 깊이와 함께 Queue에 담는다.
Queue에 들어간 단어들은 지났다는 표시를 한다.
Queue에 들어간 단어들을 순서대로 꺼내주면서 하나의 글자만 차이가 나는 단어들을 찾는 과정을 반복한다.
만약 단어가 target과 동일하다면 깊이를 출력한다.

코드

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        
        if (!Arrays.asList(words).contains(target)) {
            return 0;
        }
        
        Queue<Node> queue = new LinkedList<>();
        
        Node start = new Node(begin, 0);
        queue.offer(start);
        
        boolean[] visited = new boolean[words.length];
        
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            String word = node.getWord();
            int depth = node.getDepth();
            
            if (word.equals(target)) {
                return depth;
            }
            
            for (int i = 0; i < words.length; i ++) {
                if (!visited[i] && isOneLetterDiff(word, words[i])) {
                    queue.offer(new Node(words[i], depth+1));
                    visited[i] = true;
                }
            }
        }
        
        return answer;
    }
    
    private final boolean isOneLetterDiff (String word, String targetWord) {
        int count = 0;
        
        for (int i = 0; i < word.length(); i ++) {
            if (word.charAt(i) != targetWord.charAt(i)) {
                count ++;
            }
        }
        
        return count == 1;
    }
}

class Node {
    String word;
    int depth;
    
    Node (String word, int depth) {
        this.word = word;
        this.depth = depth;
    }
    
    public String getWord () {
        return word;
    }
    
    public int getDepth () {
        return depth;
    }
    
}

결과

느낀 점

java가 객체 지향 프로그래밍이기 때문에 클래스와 같은 것을 잘 이용할 수 있다는 것을 알면서도 어떤 식으로 이용해야 할지, 이용을 잘 할 수 있을지에 대한 두려움때문에 도전해보지 못했는데 이번 기회에 도전해봤다. 도전해보니 오히려 이렇게 푸는 게 더 쉽다고 느껴졌고 잘 활용할 수 있을 것 같다는 자신감이 생겼다.