[programmers] 단어 변환

문제 풀이 : 2021.05.05

풀이

String 배열에 담긴 단어들이 서로 변환 가능한지 확인해야 함
각 단어들 = 그래프의 노드
변환가능 여부 = 간선으로 연결여부
1) 각 단어들이 변환 가능한지 판단
2) target이 words에 없다면 0 반환하고 종료
3) begin부터 dfs 순회하면서 target이 될 때까지 순회한 노드의 수들 중에 최솟값을 반환

코드

import java.util.*;
class Solution {
    static int[][] table;
    static boolean[] visit;
    static ArrayList<char[]> c = new ArrayList<>();
    static int arrive = -1;
    static int answer = 10;
    static boolean check;
    public int solution(String begin, String target, String[] words) {
        
        table  = new int[words.length+1][words.length+1];
        visit = new boolean[words.length+1];
        c.add(begin.toCharArray());
        
        for(int i = 0;i<words.length;i++){
            if(words[i].equals(target))
                arrive = i+1;
            char[] arrChar = words[i].toCharArray();
            c.add(arrChar);
        }
        if(arrive == -1) return 0;
        
        for(int i = 0;i<c.size()-1;i++){
            for(int j = i+1;j<c.size();j++){
                if(check(c.get(i), c.get(j))){
                    table[i][j] =1;
                    table[j][i] =1;
                }
            }
        }

        visit[0] = true;
        dfs(0,0);
        if(!check) return 0;
        else return answer;
    }
    static void dfs(int node, int num){    
        if(node == arrive){
            check = true;
            answer = Math.min(answer,num);
        }
        else{
            for(int i = 0;i<table.length;i++){
                if(table[node][i] == 1 && !visit[i]){
                    visit[i] = true;
                    dfs(i, num+1);
                    visit[i] = false;
                }
            }
        }
    }
    
    static boolean check(char[] a, char[] b){
        int dif = 0;
        for(int i = 0;i<a.length;i++){
           if(a[i]!=b[i])
               dif++;
        }
        if(dif<=1) return true;
        else return false;
    }
}

문제 출처 링크