(Java) 프로그래머스 - 단어 변환

DFS / BFS 둘 중 편한 것을 선택해서 풀 수 있는 문제였다.

DFS가 더 편해 보여서 DFS를 이용해서 풀었는데 로직을 설계하는 게 어려워서 꽤 고민하며 풀었었다.

테스트 케이스도 5개밖에 되지 않고, 입력값이 크지 않아서 수행 시간은 생각하지 않고 풀었다.

---

로직

먼저 words와 동일한 크기로 방문 배열을 초기화한다.

다음으로 target 문자열이 words 배열에 있는지 검사한다.

target 문자열이 words에 없다면 바로 0을 반환하고 탐색하지 않는다.

그리고 DFS 탐색을 시작하는데 begin 문자열이 target 문자열과 몇 글자가 다른지 확인한다.

만약 한 글자만 다르다면 한 번만 변환하면 되므로 리스트에 cnt + 1 값을 저장한다.

한 글자 이상이 다르다면 words 배열을 순회하며

한 글자만 다른 문자열이 나오면 begin을 words의 문자열로 바꾸고 재귀 탐색한다.

모든 탐색이 끝나면 리스트에서 최솟값을 answer에 대입하고 반환하면 된다.

 

최종 코드

import java.util.*;
class Solution {
    static List<Integer> list;
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        // 단계를 저장할 리스트
        list = new ArrayList<>();
        // 방문 여부 배열
        boolean[] visited = new boolean[words.length];

        // target이 words 있는지 검사
        boolean flag = false;
        for (int i = 0; i < words.length; i++) {
            if(target.equals(words[i])) {
                flag = true;
                break;
            }
        }
        // target이 words 배열에 없다면 0 리턴
        if(!flag) {
           return answer;
        }

        // dfs 탐색
        dfs(begin, target, words, visited, 0);

        // 리스트에서 최솟값이 정답
        answer = Collections.min(list);
        return answer;
    }
    static void dfs(String begin, String target, String[] word, boolean[] visited, int cnt) {
        int temp = 0;
        // 현재 문자열과 target 문자열 비교
        for (int i = 0; i < word[0].length(); i++) {
            if (begin.charAt(i) != target.charAt(i)) {
                temp++;
            }
        }
        // 현재 문자열이 target 문자열과 한글자만 다르다면
        if (temp == 1) {
            // cnt값 리스트에 저장
            list.add(cnt + 1);
        }

        // words 배열을 순회하며 현재 문자열과 words의 문자열 비교
        for (int i = 0; i < word.length; i++) {
            int dif = 0;
            for (int j = 0; j < word[0].length(); j++) {
                if (begin.charAt(j) != word[i].charAt(j)) {
                    dif++;
                }
            }
            // 현재 문자열이 words 문자열과 한글자만 다르고 방문하지 않았다면
            if (dif == 1 && !visited[i]) {
                // 방문 처리
                visited[i] = true;
                // 재귀 호출
                dfs(word[i], target, word, visited, cnt + 1);
            }
        }
    }
}