[프로그래머스] 단어 변환(DFS)::알고리즘

목표: begin 단어로 시작해서 철자 1개만 변형시켜서 target 단어까지 만들어 내는 것

 

words에 있는 단어들을 사용해야 한다.

 

ex1) begin = "hit"

      target = "cog"

      words = "hot", "dot", "dog", "lot", "log", "cog"

 

정답 : hit -> hot -> dot -> dog -> cog

          0         1         2         3         4    => return 4

 

public int answer;
public boolean[] v;

public void dfs(String begin, String target, String[] words) {
  if (begin.equals(target)) {
    int cnt = 0;
    
    for (int i = 0; i < words.length; ++i) {
      if (v[i]) ++cnt;
    }
    
    answer = answer > cnt ? cnt : answer;
    return;
  }
  
  for (int i = 0; i < words.length; ++i) {
    if (v[i]) continue;
    
    int match = words[i].length();
    int cnt = 0;
    
    for (int j = 0; j < match; ++j) {
      if (begin.charAt(j) == words[i].charAt(j))
        ++cnt;
    }
    
    if (match - 1 == cnt) {
      v[i] = true;
      dfs(words[i], target, words);
      v[i] = false;
    }
  }
}

public int solution(String begin, String target, String[] words) {
  answer = 51;
  v = new boolean[words.length];
  dfs(begin, target, words);
  return answer == 51 ? 0 : answer;
}

 

[풀이 설명]

 

일단, answer를 최댓값 + 1 인 51로 설정하고,

 

방문을 검사하는 boolean 배열 v 생성

 

target을 찾으면 return하는 dfs 함수 생성

 

여러 루트가 있기 때문에 최소값을 찾아 answer에 넣어준다.

 

재귀 for문에서는 사용한 단어가 나올 때, continue 시켜주고,

 

철자 1개만 다른지 확인한다.

 

철자 1개만 다르다면 begin 값을 변경하여 재귀 함수 호출