[Programmers: JAVA] 단어 변환

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

프로그래머스

---

 

쉬운 문제이기는 했지만 나중에 이 문제를 봤을 때 BFS로 풀 생각을 할 수 있을지는 모르겠다

경로 탐색에서는 DFS를 더 많이 쓰는 스타일이라 BFS도 함께 구현해 보아야 겠다

 

 

 

 

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

// 단어 변환
public class Solution {
    static class Word{
        String word;
        int depth;
        public Word(String word, int depth) {
            this.word = word;
            this.depth = depth;
        }
    }

    public static int solution(String begin, String target, String[] words) {
        int answer = 0;

        boolean visited[] = new boolean[words.length];
        Queue<Word> q = new LinkedList<>();
        q.add(new Word(begin, 0));

        while (!q.isEmpty()){
            Word poll = q.poll();

            for (int i = 0; i < words.length; i++) {
                if(!visited[i]){
                    String word = words[i];
                    int cnt = 0;

                    for (int j = 0; j < word.length(); j++) {
                        if(poll.word.charAt(j) != word.charAt(j)) cnt++;
                    }

                    if(cnt == 1){
                        if(word.equals(target)) return poll.depth + 1;
                        q.add(new Word(word, poll.depth + 1));
                        visited[i] = true;
                    }
                }
            }
        }

        return answer;
    }

//    public static void main(String[] args) {
//        System.out.println(solution("hit", "cog", new String[]{"hot", "dot", "dog", "lot", "log", "cog"}));
//        System.out.println(solution("hit", "cog", new String[]{"hot", "dot", "dog", "lot", "log"}));
//    }

}