[프로그래머스,Java] Level3: 단어 변환

문제분석:

 

목표:   begin 단어와   end 단어가 있으며,   단어는 한문자씩 바꿔가며 교체가가능하며,

End 단어로가는 최소 경로 단계를 구하세요.

 

 

이 문제는 완전 탐색이다.

 

최소 경로 단계를 구하는 문제이므로,  BFS가 좀 더 바람직한 풀이방식인것같다.

 

그런데 DFS 구현 난이도가 훨씬쉽다..

 

DFS와 BFS 둘다 구현하는 코드를 작성해보겠다.

 

 

DFS, BFS 공통부분:

 

문제의 조건중 단어가 1개만 바꿀수있으니   바꿀수있는지 검사하는 isChanged를 작성한다.

 

 

 

 

DFS 접근법:

 

DFS는 기본적으로  백트래킹을 사용하면서  Level(Depth 깊이)의 값을 표현할수가있다.

 

DFS의 백트래킹

DFS의 전략은   result의 크기를 매우크게잡아 

 

목표값을 찾으면   result의 값을 Math.Min으로 갱신을한다.

 

이러면 최소경로가 나온다.

 

하지만,  목표값을 못찾을경우도 존재하니,  result의 값이 그대로라면  return 0으로해준다.

 

매우 간단하다.

 

 

DFS 전체코드

import java.util.*;
 
class Solution {
    
boolean[] visited;
String end;
int result=100;
    
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        
        visited= new boolean[words.length];
        
        int level=1;
        
        end = target;
     
        dfs(begin,words,level);
        
        if(result==100){
            return 0;
        }
        
        return result;
    }
    
    public void dfs(String begin, String[] words, int level){
            
            for(int i = 0; i<words.length;i++){
                if(isChanged(begin,words[i])&&!visited[i]){   
                    
                    if(words[i].equals(end)){
                         result=Math.min(result,level);
                     }
                    
                    visited[i]=true;           
                    dfs(words[i],words,level+1);
                    visited[i]=false;
                  
                }
            }
        
 
    }
    
    
    public boolean isChanged(String begin , String word){
        
        int count=0;
        
        for(int i=0;i<begin.length();i++){
            if(begin.charAt(i)!=word.charAt(i)){
                count++;
            }
            
            if(count>1){
                return false;
            }
            
        }
        
        if(count==1){
            return true;
        }
        
        return false;
        
    }
}

import java.util.*;
 
public class StringAndIdx {
    String str;
    int idx;
    
    public StringAndIdx(String str, int idx) {
        this.str = str;
        this.idx = idx;
    }
}
 
class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        
        boolean[] visited= new boolean[words.length];
        
        Queue<StringAndIdx> que = new LinkedList<>();
        
        que.add(new StringAndIdx(begin,0));
        int level=0;
        
        while(!que.isEmpty()){
            StringAndIdx temp =que.poll();
            begin=temp.str;
            int idx= temp.idx;
            
            
            for(int i = 0; i<words.length;i++){
                if(isChanged(begin,words[i])&&!visited[i]){
                    que.add(new StringAndIdx(words[i],idx+1));   
                      
                    System.out.println(words[i]);
                    visited[i]=true;
                    
                    if(words[i].equals(target)){
                          return idx+1;
                       }
                  
                }
            }
            
         
          
        }        
        
        
        return answer;
    }
    
 
    
    public boolean isChanged(String begin , String word){
        
        int count=0;
        
        for(int i=0;i<begin.length();i++){
            if(begin.charAt(i)!=word.charAt(i)){
                count++;
            }
            
            if(count>1){
                return false;
            }
            
        }
        
        if(count==1){
            return true;
        }
        
        return false;
        
    }
}