[프로그래머스/Lv. 3] 단어 변환 (JAVA)

🔺 문제

프로그래머스

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static String begin, target;
    static String[] words;
    
    static boolean[] visited;
    static int answer = 0;
    
    public int solution(String begin, String target, String[] words) {
        this.begin = begin;
        this.target = target;
        this.words = words;        
        
        visited = new boolean[words.length];
        
        dfs(begin, 0);
        return answer;
    }
    
    private static void dfs(String begin, int depth) {
        if(begin.equals(target)) { // 종료 조건 : begin = target인 경우
            answer = depth;
            return;
        }
        
        for(int i = 0 ; i < words.length ; i++) {
            if(visited[i])  continue;
            
            int k = 0;  // 두 단어 간 같은 스펠링 갯수 세기
            for(int j = 0 ; j < begin.length() ; j++) {
                if(begin.charAt(j) == words[i].charAt(j))
                    k++;
            }
            
            // 한 글자 빼고 모두 같은 경우, 변환 가능하므로 dfs 수행
            if(k == begin.length() - 1) {
                visited[i] = true;
                dfs(words[i], depth + 1);
                visited[i] = false;
            }
        }
    }
}

 

🧩 해결 아이디어

• DFS

- 한 글자 빼고 다 같은 단어를 words에서 찾고, 방문 처리함

- depth를 증가시키며 dfs 재귀 호출

- 한 글자 빼고 모두 같은 경우, 단어 변환 가능하므로 DFS르 수행

- begin = target인 경우, 정답을 depth로 설정하고 탈출한다.

 

---

🔺 다른 풀이들

- 복습용...! 멋지시다.. 완전탐색 활용하심

[level3] 프로그래머스 - 단어 변환(JAVA)

 

- 조금 다르다

[알고리즘] 프로그래머스 - 단어 변환 - JAVA

 

- BFS와 HashSet을 활용하셨다.

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

---

💬 느낀 점

여기서 DFS를 생각한다는 것이.. 백트래킹을 생각한다는 것이..

나는 아직 멀었구나 싶다..🥺

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[프로그래머스] 단어 변환 (java)

[프로그래머스] 단어 변환 (JAVA)