프로그래머스 단어 변환(words) 정답 코드

난이도 ★★★★☆

 

문제를 보시려면 여기를 클릭

 

 

 

힌트

전형적인 너비우선탐색(BFS) 문제입니다. 최소값을 찾는 문제이므로 전역(혹은 그런느낌)으로 최소값을 저장할 변수(minCountMap)를 잘 운용하셔야 해요.   구현하실 때, 이미 방문한 녀석인지 체크할 변수가 필요할텐데 Java는 객체지향 언어잖아요? 별도 배열을 두지마시고 저처럼 객체(Word.used)로 만드시길 추천드립니다. 익숙치 않아도 노력해보시길!

 

 

 

이하는 코드입니다.

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
 
public class Solution {
    private Map<String, Integer> minCountMap;
    private int MAX_COUNT;
 
    public int solution(String start, String target, String[] words) {
        minCountMap = new HashMap<>();
        MAX_COUNT = words.length;
        Set<Word> wordSet = new HashSet<>();
 
        for (String word : words) {
            Word wordObj = new Word();
 
            wordObj.word = word;
            wordObj.used = false;
 
            wordSet.add(wordObj);
        }
 
        int answer = getMinCount(start, target, wordSet);
 
        if (answer > MAX_COUNT) { // no way
            return 0;
        }
 
        return answer;
    }
 
    private int getMinCount(String start, String target, Set<Word> words) {
        Integer minCount = minCountMap.get(start);
 
        if (minCount == null) {
            minCount = MAX_COUNT + 1;
        }
 
        for (Word word : words) {
            if (word.used || !isNext(start, word.word)) {
                continue;
            }
 
            if (target.equals(word.word)) {
                minCount = 1;
                break;
            }
 
            word.used = true;
            int count = getMinCount(word.word, target, words) + 1;
            word.used = false;
 
            if (count < minCount) {
                minCount = count;
            }
        }
 
        minCountMap.put(start, minCount);
        return minCount;
    }
 
    private boolean isNext(String a, String b) {
        int diffCount = 0;
 
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                diffCount++;
 
                if (diffCount > 1) {
                    return false;
                }
            }
        }
 
        return true;
    }
 
    private class Word {
        String word;
        boolean used;
 
        @Override
        public int hashCode() {
            return word.hashCode();
        }
    }
}