알고리즘 공부

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

컴퓨터과학 2023. 10. 20. 23:46

https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=java

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

자바로 풀어봤습니다.  쉽네요 백트래킹 문제 

import java.util.*;
class Solution {
    public static String gbegin;
    public static String gtarget;
    public static String[] gwords;
    public static boolean[] gbCheck;
    public static int gn=0;
    public static int gmincnt=0;
    public Solution(){
        
    }
    
    void dfs(String start,int t ){

        for(int k=0;k<gwords.length;k++){
               int cnt=0;
               int anw=0;
            if(gbCheck[k]==false){
                for(int i=0;i<gn;i++){
                    if( start.charAt(i) == gtarget.charAt(i)){
                        anw++;
                     }
                    
                    if( start.charAt(i) == gwords[k].charAt(i)){
                        cnt++;
                     }
                
                }
                    if(anw==gn){
                        if(gmincnt==0){
                            gmincnt=t;
                        }else {
                            if(gmincnt>t){
                                gmincnt=t;
                            }
                        }
                         return ;
                    }
                    if(cnt==gn-1){
                        gbCheck[k]=true;
                        dfs(gwords[k],t+1) ;   
                        gbCheck[k]=false;
                    }

            }
             
        }
        
    }
    
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        gbegin=begin;
        gtarget=target;
        gwords=words;
        Solution s= new Solution();
        boolean[] bCheck=new boolean[words.length];
        gbCheck=bCheck;
        gn=begin.length();
        s.dfs(begin,0);
        answer=gmincnt;
        return answer;
    }
}