[프로그래머스][JAVA] 단어변환 - DFS/BFS

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

프로그래머스

 

 

 

 

1. 백트래킹(dp) 풀이(재귀를 활용한 풀이)  

import java.util.*;

class Solution {
    String target;
    String [] words;
    int answer = Integer.MAX_VALUE;
    boolean [] visited;
    int result=0;
    
    public int solution(String begin, String target, String[] words) {
        
        this.target = target;
        this.words = words;
    
        visited = new boolean[words.length];
        dp(begin,0);       
        
        
        return answer == Integer.MAX_VALUE ? 0 : answer;
    }
    
    // 재귀로 확인할 예정
    void dp(String curr, int depth){

		// target과 단어가 같으면 answer 업데이트
        if(curr.equals(target)){
            answer = Math.min(answer,result);

            return;
        }
       
        
        for(int i=0; i<words.length; i++){
        	// 방문하지 않았으면 방문 체크 후 재귀 -> 되돌려주는 것 잊지말 것!
            if(!visited[i]){
                if(isDiff(curr,words[i])){
                    visited[i] = true;
                    result++;
                    dp(words[i],depth+1);
                    visited[i] = false;
                    result--;
                }
            }
        }
    }
    
    // 단어 철자 하나만 바뀌는지 확인하는 함수
    boolean isDiff(String curr, String next){
        int count = 0;
        
        for(int i=0; i<curr.length(); i++){
            if(curr.charAt(i) == next.charAt(i)){
                count ++;
            }
        }
        
        return count == curr.length()-1;
    }
}

 

 

 

 

 

2.bfs 풀이

import java.util.*;

class Solution {

	// node는 현재 단어, distance는 바뀐 횟수
    class Node{
        String node;
        int distance;
        
        public Node(String node, int distance){
            this.node = node;
            this.distance = distance;
        }
    }
    
    int n;
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        n = begin.length();
        boolean [] visited = new boolean[words.length];
            
        // 첫 시작하는 단어는 begin, 변경 횟수는 0
        Deque<Node> q = new ArrayDeque<>();
        q.offerLast(new Node(begin,0));
        
        while(!q.isEmpty()){
            Node curr = q.pollFirst();
            
            // target과 단어가 같아지면 answer 업데이트
            // bfs 사용하므로, Math.min을 사용하지 않아도 알아서 최단거리로 갱신
            if(curr.node.equals(target)){answer = curr.distance;}
            
            for(int i=0; i<words.length; i++){
                if(!visited[i] && isDiff(curr.node,words[i])){
                	// 방문 배열 체크 ! 
                    visited[i] = true;
                    q.offerLast(new Node(words[i], curr.distance+1));
                }
            }
        }
        return answer;
    }
    
    // 철자가 하나만 달라졌는지 확인하는 함수
    boolean isDiff(String current, String next){
        int count = 0;
        
        for(int i=0; i<n; i++){
            if(current.charAt(i) == next.charAt(i)){
                count++;
            }
        }
        
        return count == n-1;
    }
}

 

 

 

 

❤ 회고

나는 dfs가 익숙해서 자꾸 dfs로만 접근하게 되는데, 다른 사람 풀이보고 bfs로도 풀어보았다 ! 

최단 거리는 bfs 최단거리는 bfs... 최단거리는 bfs.....!!!!!