프로그래머스 DFS Level 3 (단어 변환)

문제

---

두 개의 단어 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 합니다.

 

 

풀이

---

너비우선탐색으로도 풀 수 있지만, 깊이 우선탐색으로 풀었다.

 

전체 words를 돌면서 1개의 알파벳만 다른 words만 들어갈 수 있게 한다.

for(int j = 0 ; j < begin.length(); j++){
	if(words[i].charAt(j) != begin.charAt(j)){
		count++;
	}                    
}
if(count == 1){
	int result = dfs(words, i, 1, target);
    if(result != 0){
    	answer = result;
        break;
    }
}

하지만 result = 0 이 나올경우는 words를 끝까지 돌았으나 해당 문자가 targe이 아닐경우 return 0 을 하기 때문에

 

0일 경우는 제외한다.

 

위에서 단어가 하나가 다르면 dfs 메소드를 호출하는 코드는 같으나.

최소변경 횟수를 찾는 것이기 때문에 result 가 제일 작은 것을 return 하게 한다.

public int dfs(String[] words, int now, int answer, String target){
    if(visited[now])
        return 0;
        
    if(target.equals(words[now])){
        return answer;
    }
      
    int now_result = 0;
    int result = Integer.MAX_VALUE;
     
    visited[now] = true;        
      
    for(int i = 0 ; i < words.length ; i++){
        int count = 0;
        if(now != i && words[now].length() == words[i].length()){
            for(int j = 0 ; j < words[now].length(); j++){
                if(words[now].charAt(j) != words[i].charAt(j)){
                    count++;
                }
            }
             
            if(!visited[i] && count == 1){
                now_result = dfs(words, i, answer + 1, target);
                 
                if(now_result != 0 && result > now_result){
                    result = now_result;
                }
            }
        }            
    }
      
    visited[now] = false;
    if(result == Integer.MAX_VALUE)
        result = 0;
    
    return result;
}

 

 

<전체 코드>

class Solution {
    boolean[] visited;
    
    public int solution(String begin, String target, String[] words) {
        int answer = 0;

        visited = new boolean[words.length];
        for(int i = 0 ; i < words.length ; i++){
            int count = 0;
            if(words[i].length() == begin.length()){
                for(int j = 0 ; j < begin.length(); j++){
                    if(words[i].charAt(j) != begin.charAt(j)){
                        count++;
                    }                    
                }
                if(count == 1){
                    int result = dfs(words, i, 1, target);
                    if(result != 0){
                        answer = result;
                        break;
                    }
                }
            }
            
        }
        
        return answer;
    }
    
    public int dfs(String[] words, int now, int answer, String target){
        if(visited[now])
            return 0;
    
        if(target.equals(words[now])){
            return answer;
        }
        
        int now_result = 0;
        int result = Integer.MAX_VALUE;
        
        visited[now] = true;        
        
        for(int i = 0 ; i < words.length ; i++){
            int count = 0;
            if(now != i && words[now].length() == words[i].length()){
                for(int j = 0 ; j < words[now].length(); j++){
                    if(words[now].charAt(j) != words[i].charAt(j)){
                        count++;
                    }
                }
                
                if(!visited[i] && count == 1){
                    now_result = dfs(words, i, answer + 1, target);
                    
                    if(now_result != 0 && result > now_result){
                        result = now_result;
                    }
                }
            }            
        }
        
        visited[now] = false;
        if(result == Integer.MAX_VALUE)
            result = 0;
        
        return result;
    }
}