프로그래머스 dfs bfs 단어 변환

문제 링크

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.
   예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

풀이

문제를 보고 푸는 방식을 설계한 로직대로 답이 나온 문제이다. 근데 그것을 구현하는데 자잘한 오류들이있어서 애를 먹었다. dfs방식으로 푼이유는 단어 변환시 단 한개의 알파벳만 변활한 수 있는데 변환하면서 target 문자까지 도달하기 위해 수직적으로 새로운 경우의 수를 추가하는 것이 직감적으로 그려졌기 때문이다. 일반적인 dfs처럼 boolean[] visit을 선언해 이미 방문한 노드는 다시 방문하지 않도록 했지만 단순한 연결이 아니라 경우의 수 중에서 최소 값을 찾기 위한 dfs이므로 다시 visit[i]를 초기화 했다.

코드

import java.util.*;
class Solution {
   static boolean[] visit;
   static int c;
   public int solution(String begin, String target, String[] words) {
       c = 50;
       int len = words.length;
       
       visit = new boolean[len];
       dfs(begin, target, words, 0);
       return  c==50? 0: c;
       
   }
   static void dfs(String begin, String target, String[] words, int count){
       if(begin.equals(target)) {
          c= Math.min(c, count);
           System.out.print(c);
       }
       for(int i=0;i<words.length;i++){
           if(checkDiff(begin, words[i])&&!visit[i]){
               visit[i]=true;
               dfs(words[i],target, words, count+1);
               visit[i]=false;
           }
       }
   }
   static boolean checkDiff(String first, String second){
       int diff =0;
       boolean check= false;
       for(int i=0; i< first.length();i++){
           if(first.charAt(i)==second.charAt(i)) {
               diff++;
           }
       }
       if(diff==first.length()-1) check =true;
       return check;
   }
}