단어 변환(프로그래머스-DFS/BFS)

문제

코드

class Solution {
    int answer = Integer.MAX_VALUE;
    public int solution(String begin, String target, String[] words) {
        boolean[] visited=new boolean[words.length];
        for(int i=0;i<words.length;i++){
            if(words[i].equals(target)){
                dfs(begin,target,0,visited,words);
                break;
            }
        }
        if(answer==Integer.MAX_VALUE) return 0;
        return answer;
    }
    public void dfs(String word, String target,int count,boolean[] visited,String[] words){
        if(word.equals(target)){
            answer=Math.min(answer,count);
            return;
        }
        
        for(int i=0;i<words.length;i++){
            if(visited[i]) continue;
            int difference=0;
            for(int j=0;j<target.length();j++){
                if(word.charAt(j)!=words[i].charAt(j)) difference++;
            }
            if(difference==1){
                boolean[] visit=visited.clone();
                visit[i]=true;
                dfs(words[i],target,count+1,visit,words);
            }
        }
    }
}

풀이

(1) words 배열 안에 target이 존재하면, dfs() 함수를 호출한다.
(2) dfs()함수에서는 다음을 실행한다.

• 입력으로 받아온 단어가 target과 일치하면, count와 answer을 비교하여 최솟값을 갱신한다.
• words배열을 하나씩 돌면서 방문하지 않았고, word와 한글자만 다른 단어라면 방문 처리 후 count+1을 하여 dfs()를 재귀호출 한다 .

(3) 모든 탐색이 종료되면 answer을 반환한다.

결과

처음에 문제를 보고서는 어려울 것이라 생각했다.
그리고 제한사항을 봤는데, 단어 수와 단어 길이의 제한이 너무 작았기 때문에 무조건 dfs로 풀 수 있겠다 생각했다.
words 배열의 길이도 짧고, 단어의 길이도 짧기 때문에 한글자만 다른 단어가 있는지 찾는 것도 그냥 모두 확인해 주면 됐다.
기계처럼 dfs 구현하고 제출 했더니 한번에 성공했다.
나는 dfs 문제가 너무 좋다. 모든 경우의 수 찾아주면 되니, 너무 편하다.
출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges