[프로그래머스 (Java)] 단어변환

 

https://programmers.co.kr/learn/courses/30/lessons/43163?language=java 

코딩테스트 연습 - 단어 변환

단어를 변환하는데 필요한 최소 횟수를 반환하는 문제이기 때문에 bfs 를 이용해 모든 경우를 확인하다가 단어를 바꿀 수 있는 tree 의 depth 를 반환하는 방식으로 코드를 작성할 수 있습니다.

import java.util.*;

class Solution {
    public boolean canChange(String from, String to) {
        int count = 0;
        if (from.length() != to.length()) {
            return false;
        }
        for (int i = 0; i < from.length(); i++) {
            if (from.charAt(i) != to.charAt(i)) {
                count += 1;
            }
            if (count > 1) {
                return false;
            }
        }
        return count == 0 ? false : true;
    }

    public int bfs(int count, String target, Set<String> prev, Set<String> unchecked) {
        Set<String> next = new HashSet<>();
        for (String p : prev) {
            for (Iterator<String> iter = unchecked.iterator(); iter.hasNext(); ) {
                String n = iter.next();
                if (canChange(p, n)) {
                    next.add(n);
                    iter.remove();
                }
            }
        }
        count++;
        if (next.isEmpty()) {
            return 0;
        }
        if (next.contains(target)) {
            return count;
        }
        return bfs(count, target, next, unchecked);
    }

    public int solution(String begin, String target, String[] words) {
        Set<String> start = new HashSet<>(Collections.singletonList(begin));
        Set<String> unchecked = new HashSet<>(Arrays.asList(words));
        if (!unchecked.contains(target)) {
            return 0;
        }
        return bfs(0, target, start, unchecked);
    }
}