[프로그래머스 고득점 Kit] 단어 변환 DFS/BFS 자바 풀이 및 정답, 테스트 케이스

문제요약)

- 시작단어, 타겟단어가 주어짐

- 주어지는 단어리스트를 통해 시작단어부터 타겟단어까지 변환시키기

- 한번에 한 글자만 바꿀 수 있음

 

주의점)

- DFS를 쓴다면 단어 사용후 백트래킹 할 때 사용한 단어 초기화

- BFS를 쓰는 경우 최단 거리만 찾으면 되기에 크게 중요x

 

풀이)

dfs, bfs 둘 다 괜찮게 사용이 가능한 문제입니다.

다만, 최단 거리를 구하는 문제인 만큼 웬만해서는 bfs를 쓰는게 효율성은 더 잘나오게 됩니다.

 

1. DFS

-> boolean배열 혹은 HashMap을 통해 사용한 단어 구분

-> 사용한 단어가 아니고, 다음단어로 갈 수 있는 단어면 DFS이어서 진행

-> 사용한 단어 표기 해제

package programmers.kit.dfsbfs;

import java.util.HashMap;

public class ChangeWord2_DFS {
    static int answer = 999;
    static HashMap<String, Boolean> visit = new HashMap<>();
    public static void main(String[] args) {
    }

    public static int solution(String begin, String target, String[] words) {
        // DFS로 풀이
        DFS(0, begin, target, words);
        if (answer == 999) answer = 0;
        return answer;
    }

    static void DFS(int depth, String currentWord, String target, String[] words) {
        // 방문한 단어 체크
        visit.put(currentWord, true);
        if (currentWord.equals(target)) {
            answer = Math.min(answer, depth);
        }
        if (depth > words.length - 1) return;

        // 방문 가능한지 체크
        for (int i=0; i<words.length; i++) {
            int canNext = 0;
            String a = words[i];
            // 방문 안한 단어면 다음 단어로 가능한지 체크 후 방문
            if (!visit.getOrDefault(a, false)) {
                for (int j=0; j<a.length(); j++) {
                    if (currentWord.charAt(j) != a.charAt(j)) {
                        canNext++;
                    }
                }
                if (canNext == 1) {
                    DFS(depth + 1, words[i], target, words);
                    visit.put(words[i], false);
                }
            }
        }
    }

}

 

2. BFS

-> boolean배열을 통해 사용한 단어 구분

-> 사용한 단어가 아니고, 다음단어로 갈 수 있는 단어면 q에 넣어서 다음 BFS 진행

-> 최단 거리만 구하면 되므로 사용한 단어 표기 해제 불필요

import java.util.*;

public class ChangeWord3_BFS {
    public static void main(String[] args) {
    }

    public static int solution(String begin, String target, String[] words) {
        int answer = 0;
        // BFS 풀이
        // visited 초기화가 불필요한 이유는 최단거리만 따지기 때문에
        // 불필요하게 경유하는 경우는 필요가 없음
        Queue<String> q = new LinkedList<>();
        boolean[] visited = new boolean[words.length];

        q.offer(begin);

        while (!q.isEmpty()) {
            int size = q.size();

            for (int j=0; j<size; j++) {
                String currentWord = q.poll();

                // 타겟과 같으면 answer
                if (currentWord.equals(target)) {
                    return answer;
                }

                // 방문 안했는지 체크, 다음 단어로 가능한지 체크
                for (int i=0; i<words.length; i++) {
                    boolean canNext = canNext(currentWord, words[i]);
                    if (!visited[i] && canNext) {
                        visited[i] = true;
                        q.offer(words[i]);
                    }
                }
            }

            answer++;
        }
        return 0;
    }

    static boolean canNext(String currentWord, String nextWord) {
        int diffCount = 0;
        for (int i=0; i<currentWord.length(); i++) {
            if (currentWord.charAt(i) != nextWord.charAt(i)) {
                diffCount++;
            }
        }
        return diffCount == 1;
    }

}