[자바 / Java] 프로그래머스 - 단어변환 (BFS/ DFS)

https://school.programmers.co.kr/learn/courses/30/lessons/43163

프로그래머스

 

문제설명

 

두 개의 단어 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 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

예제 #1
문제에 나온 예와 같습니다.

예제 #2

 

 

구현코드 &설명 (DFS)

class Solution {
    public int solution(String begin, String target, String[] words) {
        String now = begin; // 바뀐 문자
        int count=0;
        int[] visited = new int[words.length];
        // words문자열의 방문여부를 체크하는 배열
        
        
        return dfs(now, target, words, visited, count);
        
        // dfs
        // 만약 now 문자와 target문자가 같으면 count를 return
        // 만약 now 문자와 target문자가 같지 않으면 
        // words문자열 중에서 하나의 char만 다른것이 있는지 찾고
        // 하나의 char만 다른 문자가 있다면 해당 문자를 now로 바꾸고
        // visited에서 words배열 중 그 문자를 사용처리
    }

    public int dfs(String now, String target, String[] words, int[] visited, int count){
            
            if(count == words.length) return 0;
            if(now.equals(target)) return count;
            else {             
                
                int min = Integer.MAX_VALUE;
                int [] dfs_visited=visited.clone();
                 // words배열의 각 인덱스를 돌면서
                // 하나의 문자만 다른지 판단
               // 만약 하나만 다르면 dfs호출
                for(int i=0; i<words.length; i++){
                    int diff = 0; // 문자가 바뀔떄마다 초기화    
                    for(int j=0; j<now.length(); j++){

                        if(words[i].charAt(j) != now.charAt(j)) diff++;
                    }
                    // 하나만 다르고, 해당 words를 방문한 적이 없으면
                    if(diff == 1 && dfs_visited[i] == 0) {
                        //now = words[i]; //words[i]로 now를 바꾸고
                        dfs_visited[i] = 1; // 방문처리
                        int result = dfs(words[i], target, words, dfs_visited, count+1);
                        
                        if(min > result && result != 0) min =result; 
                        dfs_visited[i] = 0; // 방문처리된 것은 자식노드들만 공유해야하고
                        					// 다른 형제노드들은 영향을 받지 않아야하므로
											// 다시 0으로 되돌리기                        
                    }
                }
                
                if(min == Integer.MAX_VALUE) {
                    return 0;
                }else{
                    return min;
                }               
            }
        }
        
         

        
    }

구현코드 &설명 (BFS)

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        Queue<Status> que = new LinkedList<>(); 
        int count = 0; 
        int minCount = Integer.MAX_VALUE;
        int[] visited = new int[words.length];
        
        // words를 탐색하며
        // begin에서 한 글자만 바꾸면 target이 되는 문자열을
        // que에 삽입
        for(int i=0; i<words.length; i++){
            int diff =countDiff(begin, target, words[i]);
            if (diff == 1){
                visited[i] =1; 
                que.add(new Status(words[i], count+1, visited.clone()));
                visited[i]=0;
            }            
        }
        
        while(!que.isEmpty()){
           Status s =  que.poll();
           if(s.now.equals(target) && s.count <= words.length){ 
               // 만약 뽑은 값이 target과 같고, 비교횟수가 words의 길이 미만이라면
               // count 와 minCount를 비교, 더 작은 값을 minCount에 대입
               if(minCount > s.count) minCount = s.count;
               break;         
           } 
            for(int i=0; i<words.length; i++){                
                if( s.visited[i] ==0) {
                    int diff = countDiff(s.now, target, words[i]);
                    if (diff == 1 ) {
                    s.visited[i] =1; 
                    que.add(new Status(words[i], s.count+1, s.visited.clone()));
                    s.visited[i]=0;
                }
                    
                }

            }
        }    
        
        if(minCount ==  Integer.MAX_VALUE ) return 0;
        
        return minCount;
    }
  
    //시작단어, target단어, 현재단어를 입력받고 begin단어와 current단어 구성 중 
    // 몇 개의 문자가 다른지 판단하는 함수
    // 두 문자 중 차이나는 알파벳 수 diff를 리턴
    public int countDiff(String begin, String target, String currentWord){

        int diff = 0;
        for(int i=0; i< begin.length(); i++){
             if(currentWord.charAt(i) != begin.charAt(i)) diff++;            
        }
        
        return diff;
    
    }
    
}

// que에 삽입되는 객체
class Status {
    String now; // 현재단어 
    int count; // 총 변환횟수 
    int[] visited; // 방문한 words배열 체크
    public Status (String now, int count, int[] visited){
        this.now = now;
        this.count = count;
        this.visited = visited; 
    }
    
}