[DFS/BFS] 단어 변환 - JAVA

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

프로그래머스

---

처음에 보고 bfs로 풀려고 했는데 dfs로도 충분히 풀리더라구!

 

이 문제는 시작점과 끝점이 정해져 있어서 반복문으로 dfs를 호출할 필요는 없다!

 

문제에서 begin에서 target까지 몇 번 바뀌었는지 확인만 하면 되는거라 count를 통해서 바뀐 횟수를 구했다

 

dfs는 재귀호출이라 탈출 조건이 필요하니까 탈출 조건은 begin과 target이 같을 때로 해준다

그리고 반복문을 돌면서 다음 word로 넘어갈 수 있는지 검사하며 조건은 다음과 같다

 

• 방문한 적 없는 word
• 이전 word와 한 글자만 차이나는가

 

요 2개를 검사해주고 조건이 맞으면 dfs를 재귀호출한다

재귀호출할 때는 begin 부분은 현재 word로, count는 1을 증가시켜준다!

 

 

 

 

 

자바 코드)

class Solution {
    static boolean[] visited;
    static int answer = 0;
    public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];
        dfs(begin, target, words, 0);
        return answer;
    }

    public static void dfs(String begin, String target, String[] words, int count) {
        if(begin.equals(target)) {
            answer = count;
            return;
        }

        for(int i=0;i<words.length;i++) {
            if(visited[i]) continue;

            int len = 0;
            for(int j=0;j<begin.length();j++) {
                if(begin.charAt(j) == words[i].charAt(j)) {
                    len++;
                }
            }

            if(len == begin.length()-1) { // 한 글자만 다른 경우
                visited[i] = true;
                dfs(words[i], target, words, count+1);
                visited[i] = false; // 다시 탐색을 위해서 방문 처리 초기화
            }
        }
    }
}