[Programmers] 단어 변환

난이도 : Level 3

문제링크

• 문자열 begin, target과 문자열 배열 words가 주어진다
• 주어진 변환과정을 사용하여 begin에서 target으로 변환하는 최소한의 단계수를 리턴하라
• 변환 제약사항
  • 한 번에 한 개의 알파벳만 바꿀 수 있음
  • words에 있는 단어로만 변환할 수 있음
• example
  • "hit" "cog" ["hot", "dot", "dog", "lot", "log", "cog"]
  • "hit" -> "hot" -> "dot" -> "dog" -> "cog"
  • => 4

 

해설

• BFS 탐색을 하여 모든 경우의 수를 찾는다.
• 큐 자료구조를 사용하므로, 너비 탐색중에 target이 만들어지는 가장 최근의 변환횟수가 가장 최소의 변환횟수이다.
• 큐에 들어갈 단어가 유효성 검사를 통과해야 큐에 들어갈 수 있다.
  • 현재 뽑은 단어와 비교하였을 때 글자의 차이수가 한글자인지 확인한다
• 이전에 큐에 들어간 단어는 다시 들어가지 못하게 하여 사이클을 방지한다.

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {        
        Queue<Map<Integer, Object>> queue = new LinkedList<>();
        for (String word : words) {
            if (isOneDiscrepency(begin, word)) {
                queue.offer(createMap(word, 1));                
            }
        }
        
        Set<String> visited = new HashSet<>();
        visited.add(begin);
        
        while (!queue.isEmpty()) {
            Map<Integer, Object> node = queue.poll();
            String qword = (String) node.get(0);
            int turn = (int) node.get(1);
            if (qword.equals(target)) {
                return turn;
            }   
            
            for (String word : words) {
                if (isOneDiscrepency(qword, word) && !visited.contains(word)) {
                    visited.add(word);
                    queue.offer(createMap(word, turn+1));
                }
            }
        }

        return 0;
    }
    
    private boolean isOneDiscrepency(String begin, String next) {
        int count = 0;
        for (int i = 0; i < begin.length(); i++) {
            if (begin.charAt(i) != next.charAt(i)) {
                if (count > 0) {
                    return false;
                }
                
                count++;
            }
        }
        
        return true;
    }
    
    private Map<Integer, Object> createMap(String word, int turn) {
        Map<Integer, Object> map = new HashMap<>();
        map.put(0, word);
        map.put(1, turn);        
        
        return map;
    }    
}