[프로그래머스]단어 변환 - Java

문제

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

프로그래머스

 

 

풀이

Level 3 문제치고 흔한 dfs 문제라고 생각이 들었음

 

알파벳이 바뀌는 횟수를 세는 부분이 포인트인 것 같음 !

 

자세한건 주석으로 !

 

 

코드

// 코딩테스트 연습 - 깊이/너비 우선 탐색(DFS/BFS) - 단어 변환
// https://school.programmers.co.kr/learn/courses/30/lessons/43163

package PROGRAMMERS.level3;

public class Num43163_단어변환 {
    private static class Solution {
        static int min; // 정답(최솟값)
        static boolean[] visited; // 방문 체크 배열
        private int solution(String begin, String target, String[] words) {
            int answer = 0;
            min = Integer.MAX_VALUE;
            visited = new boolean[words.length];

            if (isPossible(words, target)) { // 가능하면 dfs
                dfs(0, begin, target, words);
                answer = min; // 정답 최신화
            }

            return answer;
        }

        private void dfs(int depth, String current, String target, String[] words) {
            // 탈출 조건(현재 단어가 target과 같으면 min값 갱신)
            if (current.equals(target)) {
                min = Math.min(min, depth);
            }

            // 탈출 조건
            if (depth > words.length) {
                return;
            }

            // words를 하나씩 뽑아서 비교
            for (int i = 0; i < words.length; i++) {
                int count = 0; // 알파벳 바뀐 횟수 측정

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

                // 알파벳이 한번만 바뀌었고, 아직 방문하지 않았으면 dfs(depth + 1, ...)
                if (count == 1 && !visited[i]) {
                    visited[i] = true; // 방문 체크
                    dfs(depth + 1, words[i], target, words);
                    visited[i] = false; // 방문 체크 해제
                }
            }
        }

        // words 배열에 target과 같은 단어가 있는지 판별
        private boolean isPossible(String[] words, String target) {
            boolean flag = false;
            for (String str : words) {
                if (target.equals(str)) {
                    flag = true;
                    break;
                }
            }

            return flag;
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        System.out.println(sol.solution("hit", "cog", new String[]{"hot", "dot", "dog", "lot", "log", "cog"}));
        System.out.println(sol.solution("hit", "cog", new String[]{"hot", "dot", "dog", "lot", "log"}));
    }
}