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

첫 시도

• dfs와 백트래킹을 이용하여 문제를 해결
• 먼저 word 배열 순회하면서 begin과 다른 단어가 1개인지 확인 → 배열의 크기 n이 50, 문자열의 길이m이 10까지라서 완전탐색 사용가능 → O(n^2m) → 2,500번
• bfs가 아닌 dfs를 사용하므로 다시 return하기 전에 배열은 false로 바꿔줘야함(백트래킹)
• begin과 target이 같으면 해당 count를 return
• begin을 전역변수로 두고 사용하다가 채점 시 오답으로 나옴 → 백트래킹 하면서 begin을 다시 되돌려놓지 않음 → 함수 파라미터로 begin을 넘겨줌 → 백트래킹 시 자동으로 되돌려짐 → 해결

  해결

• 내용

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;


class Solution {
    String target;
    String[] words;
    boolean[] check;
    int min = Integer.MAX_VALUE;
/**
     * true면 해당 단어로 바꿀 수 있음
*@paramindex
*/
boolean countDiff(int index, String begin){
        boolean result = false;
        int count = 0;
        String temp = words[index];
        for(int i = 0; i<temp.length(); i++){ // 최대 10번
            char a = begin.charAt(i);
            char b = temp.charAt(i);
            if(a != b) count++;
        }
        if(count == 1 ) result = true; // 다른게 하나라면 true;

        return result;
    }

    int dfs(String begin,int count){
        if(begin.equals(target)){
            return count;
        }
        for(int i = 0; i< words.length; i++){
            if(!check[i] && countDiff(i,begin)){
                check[i] = true;
                min = Math.min(min, dfs(words[i],count+1));
                check[i] = false;
            }
        }
        return min;


    }

    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        this.target = target;
        this.words = words;
        check = new boolean[words.length];
        answer = dfs(begin,0);
        if(answer == Integer.MAX_VALUE) answer = 0;
        return answer;
    }
}

참고

• 직접구현