[프로그래머스] #lv.3 - 단어 변환 (Java)

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

프로그래머스

 

# 힌트

hit 다음으로 올 수 있는 경우의 수는 hot, dot, dog, lot, log, cog 인데, 변환 조건 때문에 hot만 가능하다.

즉, 변환 가능한 단어들에 대해서 DFS를 진행하고, target 단어에 도달하면 지금까지 방문한 단어들 (깊이값)을 저장한다. 저장된 깊이값중 가장 작은 값을 찾으면 된다.

방문했던 단어는 재방문을 방지하기 위해 visited를 관리해야한다. (힌트 : Map<String, Boolean>)

 

테스트케이스 3번 힌트 : 단어가 3글자 이상, 10글자 이하인 것에 주목하라. 예시 테스트케이스는 단어가 3개인 경우만 나와서 착각하기 쉽다.

 

해답 보기

import java.util.*;
import java.util.stream.*;
class Solution {

    // 결과값 저장 (최소 방문 횟수)
    static int result = Integer.MAX_VALUE;
    static Map<String, Boolean> visited = new HashMap<>();

    public static int solution(String begin, String target, String[] words) {
        // 변환할 수 없으면 0 반환
        if ((!Arrays.asList(words).contains(target))) return 0;

        // 단어 방문 여부를 저장할 map
        for (String word : words) visited.put(word, false);

        dfs(begin, target, words, 0);
        
        // dfs를 종료하면 result에 값이 저장되어 있음
        return result;
    }

    static boolean isChangeable(String from, String to, String[] words) {
        int c = 0;
        // 모든 단어의 길이가 동일하다는 조건때문에 아무 길이로 비교 가능
        for (int i = 0; i < from.length(); i++)
            if (from.charAt(i) == to.charAt(i)) c++;
        
        // 바꿀 수 있는 경우 = 두 단어가 한 글자만 다르고 words에 포함 
        return c >= from.length() - 1 && Arrays.asList(words).contains(to);
    }

    static void dfs(String cur, String target, String[] words, int depth) {
        if (cur.equals(target)) {
            // target값과 동일하면 지금까지 내려온 depth를 비교한다
            result = Math.min(result, depth);
            System.out.println("-------------");
        }
        else {
            // 현재 단어 방문 처리
            visited.put(cur, true);
            for (String word : words) {
                // 방문 하지 않았고, 변경가능한 단어를 탐색
                if (!visited.get(word) && isChangeable(cur, word, words)) {
                    System.out.println(cur + " -> " + word);
                    dfs(word, target, words, depth + 1);
                }
            }
        }
    }
}