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

프로그래머스 level3 단어변환

 

소요시간 : 16분

 

 

dfs 로 풀었다.

begin 에서 1글자만 다른 단어를 words 배열에서 찾아서 dfs 를 시작한다.

cnt 변수를 들고다니면서 dfs를 들어갈 때마다 단어변환횟수 +1 한다.

begin 이 target 과 같은 순간 종료되고 매번 cnt 가 더 작은 값으로 MIN이 업데이트 된다.

class Solution {
  boolean[] selected;
  int N;
  public int solution(String begin, String target, String[] words) {
    N = words.length;
    selected = new boolean[N];
    for (int i = 0; i < N; i++) {
      if(isDiffOne(begin, words[i])) {
        selected[i] = true;
        dfs(1, words[i], target, words);
        selected[i] = false;
      }
    }
    if(MIN == Integer.MAX_VALUE) return 0;
    return MIN;
  }
  
  int MIN = Integer.MAX_VALUE;
  public void dfs(int cnt, String begin, String target, String[] words) {
    if(begin.equals(target)) {
      if(MIN > cnt) MIN = cnt;
      return;
    }

    for (int i = 0; i < N; i++) {
      if(selected[i]) continue;
      if(isDiffOne(begin, words[i])) {
        selected[i] = true;
        dfs(cnt+1, words[i], target, words);
        selected[i] = false;
      }
    }
  }
  
  public boolean isDiffOne(String a, String b) {
    int cnt = 0;
    for (int i = 0; i < a.length(); i++) {
      if(a.charAt(i) != b.charAt(i)) cnt++;
      if(cnt > 1) return false;
    }
    return true;
  }
}