출처

해당 게시글은 [Java] 어서와! 자료구조 알고리즘은 처음이지?https://programmers.co.kr/learn/courses/13577를 간략히 요약한 게시글이며 모든 출처는 해당강의에 있습니다

---

문제

문제분석

한번에 한개의 알파벳만 바꿀 수 있고 다시 돌아가는 것은 불가능 합니다. DFS나 BFS같이 모든 경우를 따져보고 최저인 값을 구하는 문제 입니다.

---

풀이

나의 풀이

import java.util.*;
import java.util.stream.*;

class Solution {
    int answer = 51;
    
    public int solution(String begin, String target, String[] words) {
        
        boolean[] visited = new boolean[words.length];
        List<String> list = Arrays.stream(words).collect(Collectors.toCollection(ArrayList::new));
        if(!list.contains(target)) return 0;
        
        //BFS + 재귀
        bfsSearch(words, visited, 0, begin, target);
        //50개가 들어오므로 초기값이면 안나옴 -> 0
        return answer == 51 ? 0 : answer;
    }
    
    void bfsSearch(final String[] words, boolean[] visited, int count, String begin, String target){
        //종료 조건
        if(begin.equals(target)){
            if(count < answer) answer = count;
            return;
        }
        if(count == words.length){
            return;
        }
        
        //재귀 식
        for(int i = 0; i < words.length; i++){
            //아직 방문 안했고 1글자만 차이남 -> replaceAll로 나온 글자 다지우고 1글자만 남는지 확인
            if(visited[i] == false && changeable(begin,words[i])){
                //백 트래킹
                visited[i] = true;
                bfsSearch(words, visited, count+1, words[i], target); //재귀
                visited[i] = false;
            }
        }
        
    }
    
    boolean changeable(String w1, String w2){
        int length = Math.min(w1.length(), w2.length());
        int count = 0;
        for(int i = 0; i < length && count < 2; i++){
            if(w1.charAt(i) != w2.charAt(i)) count++;
        }
        
        return count == 1;
    }
}

재귀를 활용하여 모든 경우를 참조하도록 하였습니다. 또 재귀 내에서 백트래킹을 활용하여 선택한 경우, 선택하지 않은 경우로 나뉘어 경우를 구하였습니다.
begin, count 매개변수를 바꿔가며 모든 문자를 둘러본 경우, 찾은 경우 값을 반환하도록 하였습니다.

강의의 풀이

import java.util.*;

//문자를 담는 정보
class Node{
    String word; //문자
    int depth; //깊이
    Node(String word, int depth){
        this.word = word;
        this.depth = depth;
    }
}

class Solution {
    
    public int solution(String begin, String target, String[] words) {
        if(!Arrays.asList(words).contains(target)) return 0; //words에 존재하지 않는 단어
        
        Stack<Node> stack = new Stack<>();
        Set<String> used = new HashSet<>(); //이미 방문했는지 포함
        
        stack.push(new Node(begin,0));
        
        //스택이 빌 떄 까지
        while(!stack.isEmpty()){
            Node now = stack.pop();
            //target 찾음
            if(now.word.equals(target)) return now.depth;
            
            for(String word : words){
                if(used.contains(word)) continue; //이미 한번 방문함
                if(!changeable(now.word, word)) continue; //1글자 차이가 아님
                
                //깊이 +1 해서 스택에 추가
                stack.push(new Node(word, now.depth+1));
                used.add(word); //사용함 표시
            }
        }
        
        return 0;
    }
    
    boolean changeable(String w1, String w2){
        //w2와 w1의 글자가 1글자 차이인지 확인
        int length = Math.min(w1.length(),w2.length());
        int count = 0;
        for(int i = 0; i < length && count < 2; i++)
            if(w1.charAt(i) != w2.charAt(i)) count++;
        return count == 1;
    }
}

클래스를 활용하여 문자와 깊이를 각각 저장함으로써 구현을 훨씬 쉽도록 하였습니다.

그래프 배울때 사용하였던 스택과 큐를 활용한 BFS, DFS를 이용하여 문제를 해결하였습니다.

---

Github

https://github.com/ds02168/Study_Algorithm/blob/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/%5BJava%5D%20%EC%96%B4%EC%84%9C%EC%99%80%20%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%80%20%EC%B2%98%EC%9D%8C%EC%9D%B4%EC%A7%80/%ED%8C%8C%ED%8A%B88.%EA%B7%B8%EB%9E%98%ED%94%84%2CDFS%2CBFS/%EB%8B%A8%EC%96%B4%EB%B3%80%ED%99%98.java