[JAVA] 프로그래머스 : 단어 변환 (코딩테스트 고득점 kit > 깊이/너비 우선 탐색(DFS/BFS))

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

코딩테스트 연습 - 단어 변환

dfs를 이용하여 구현함

해결 방안

1. begin이 target과 같을 때의 depth와 minDepth를 비교하여 최소값을 minDepth에 저장함. 그리고 변환 과정이 words 배열의 크기보다 크면 변환할 수 없는 경우이므로 0을 저장함

2. words 전체를 돌면서 dfs를 통해 가장 짧은 변환 과정을 찾아줌
이 때, begin과 한 글자가 다른 경우에만 변환이 가능하므로 한 글자가 다른 경우에만 변환을 해줌 

 

코드

import java.util.*;

// 단어 변환
class Solution {
    
    public static int answer;
    public static boolean[] visited;
    public static int minDepth = Integer.MAX_VALUE;
    
    public static void dfs(String[] words, String begin, String target, int depth){
        //System.out.println("begin: " + begin + ", depth: " + depth);
        if(begin.equals(target)){
            
            minDepth = Math.min(minDepth, depth);
            if(minDepth > words.length)
                minDepth = 0;
            //System.out.println(minDepth);
            answer = minDepth;
            return;
        }
        
        // words 전체 돌면서 dfs를 통해 가장 짧은 변환 과정 찾기
        int cnt; 
        String temp;
        for(int i=0; i<words.length; i++){
            
            if(visited[i])
                continue;
            
            // begin과 한 단어만 다른 경우 변환 가능
            cnt = 0;
            for(int j=0; j<words[i].length(); j++){
                if(words[i].charAt(j) != begin.charAt(j))
                    cnt++;
            }
            
            // 변환 가능
            if(cnt == 1){
                visited[i] = true;
                
                dfs(words, words[i], target, depth+1);
                
                visited[i] = false;
            }
                
            
        }
        
    }
    
    public int solution(String begin, String target, String[] words) {
        answer = 0;
        visited = new boolean[words.length];
        
        for(int i=0; i<visited.length; i++){
            visited[i] = false;
        }
        
        dfs(words, begin, target, 0);
        
        return answer;
    }
}

 

두 번째 풀이

BFS를 이용하여 구현

 

코드

import java.util.*;
// 단어 변환
// begin에서 target으로 변환하는 가장 짧은 변환 과정 찾기
class Solution {
    
    static class Word{
        String text;
        int depth;
        
        Word(String text, int depth){
            this.text = text;
            this.depth = depth;
        }
    }
    
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        
        // 변환할 수 있는지 없는지 확인
        boolean flag = true;
        for(int i=0; i<words.length; i++){
            // words[]에 target 있으면 false
            if(target.equals(words[i])){
                flag = false;
                break;
            }
        }
        //target이 words[]에 없는 경우(flag==true) return 0
        if(flag) return 0;
        
        answer = bfs(begin, target, words);
        
        return answer;
    }
    
    static int bfs(String begin, String target, String[] words){
        int depth = 0;
        boolean[] visited = new boolean[words.length];
        
        Queue<Word> q = new LinkedList<>();
        q.offer(new Word(begin, 0));
        
        Word currentWord;
        String currentText;
        int currentDepth;
        while(!q.isEmpty()){
            currentWord = q.poll();
            currentText = currentWord.text;
            currentDepth = currentWord.depth;
            
            // 타겟이면 break;
            if(currentText.equals(target)){
                depth = currentDepth;
                break;
            }
            
            // 인접 노드 추가 
            int cnt; // 알파벳 차이 갯수
            for(int i=0; i<words.length; i++){
                
                if(visited[i]) continue;
                
                // 인접 노드인지 확인(알파벳 1개차이)
                cnt = 0;
                for(int j=0; j<currentText.length(); j++){
                    if(currentText.charAt(j) != words[i].charAt(j)){
                        cnt++;
                    }
                }
                
                // 인접 노드이면서 방문안한거면 q에 넣어주기
                if(cnt == 1){
                    q.offer(new Word(words[i], currentDepth+1));
                    visited[i] = true;  
                }
            }
        }
        
        return depth;
    }
}