[프로그래머스 | Java Lv.3] 단어 변환(dfs/bfs)

문제

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

프로그래머스

 

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

 

각 단어는 알파벳 소문자로만 이루어져 있습니다.
각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
begin과 target은 같지 않습니다.
변환할 수 없는 경우에는 0를 return 합니다.

 

문제랑 진짜 싸울 뻔 했다.. ㅎㅎ 내가 이김

---

접근

 

begin부터 시작해서 한 문자만 다른 글자를 찾아서 dfs를 호출하면 되지 않을까

 

먼저 begin인 "hit"은 갈 수 있는 곳이 "hot" 밖에 없다. 

"hot"은 "dot", "lot"으로 갈 수 있다.

 1. "dot"으로 갈 때 

   "lot" -> "log" -> "cog"

 2. "lot"으로 갈 때 

    "log" -> "cog" 

 

path를 기억해야 좋지 않을까 해서 path를 ArrayList로 dfs가 호출될 때마다 추가되게 했다. 

근데 정답 코드들을 보면 이게 아예 필요가 없었고, 그냥 길이만 count하면 됐었다. 

path를 저장하려다보니까 path 초기화 문제 등 푸는데 꽤 큰 어려움이 있었다

 

밑은 그렇게 path를 모두 저장하게 하고, target에 도달하게 됐을 때는 result라는 ArrayList에 path의 크기를 저장하게 하는 코드이다.

마지막은 result를 sort하고, 가장 작은 값을 return하게 한다. 

 

밑은 내 삽질 코드이고 이걸 만약 보는 사람이 있다면  절대 이렇게 풀지 마세요

---

코드

package week6.baek.dfsbfs;

import java.util.*;

public class Word {
    static boolean[] visited;
    static ArrayList<Integer> result;

    //문자 차이가 1인지 유사도를 구하는 함수
    public static boolean similarity(String target, String word){
        int count = 0;
        for (int i = 0; i < target.length(); i++) {
            if(target.charAt(i) != word.charAt(i)) count++;
        }
        if(count == 1) return true;
        else return false;
    }

    public static void dfs(String target, String[] words, String word, ArrayList<String> path){
        if(word == target) {
//            System.out.println(path);
            result.add(path.size());
            return;
        }


        for (int i = 0; i < words.length; i++) {
            if(!visited[i] && similarity(word, words[i])){
                visited[i] = true;
                path.add(words[i]);
                dfs(target, words, words[i], path);
                path.remove(path.size() - 1);
                visited[i] = false;
            }
        }

    }

    public static int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];
        result = new ArrayList<>();

        for (int i = 0; i < words.length; i++){
            if(similarity(words[i], begin)) {
                ArrayList<String> path = new ArrayList<>();
                path.add(words[i]);
                visited = new boolean[words.length];
                visited[i] = true;

                dfs(target, words, words[i], path);
            }
        }

        Collections.sort(result);
//        System.out.println(result);

        if(result.isEmpty()) return 0;

        return result.get(0);
    }

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