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

howisitgoing·2023년 4월 9일

Java 프로그래머스

프로그래머스

목록 보기

9/10

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

단어 변환

해결 방법

문제를 읽자 마자, 아 이건 DFS로 풀어야 겠구나! 라고 생각했습니다.
이 문제는 사실 프로그래머스의 여행경로와 매우 유사한 문제 라고 느꼈습니다.^^

여행경로 풀이

1트

DFS로 문제를 해결했지만, 케이스 3번에서 실패했습니다…
한참 고민했는데 잘 몰라서 결국...

2트

케이스 3번에서 실패한 이유를 프로그래머스의 질문하기 페이지를 통해서 해결했습니다!!
제가 틀린 이유는 단어를 탐색하는 과정에서 문제가 있었습니다.

반드시 단어의 위치까지 고려해서 비교해야합니다.
동일한 인덱스 끼리 비교하면 됩니다.!
(저는 charAt()을 사용 했습니다.)

DFS 경로 엿보기 👀

예제 1 입력에 대해서 다음과 같은 경로가 생성 됩니다.

hit->hot->dot->dog->log->cog
hit->hot->dot->dog->cog
hit->hot->dot->lot->log->dog->cog
hit->hot->dot->lot->log->cog
hit->hot->lot->dot->dog->log->cog
hit->hot->lot->dot->dog->cog
hit->hot->lot->log->dog->cog
hit->hot->lot->log->cog

여기서 생각해볼 것이 있는데 🤔
이전에 찾은 경로의 depth보다 새롭게 찾은 경로의 depth가 크거나 같으면 굳이 다시 탐색할 필요가 없습니다.!!👍

// 이전에 찾은 depth보다 크면 탐색할 필요가 없음
if(answer <= depth) return;

위 코드를 추가하면 아래와 같은 경로만 나오게 됩니다.^^
이렇게 하면 시간적인 효율에서 더 좋겠죠?

hit->hot->dot->dog->log->cog
hit->hot->dot->dog->cog

풀이

class Solution {
    int answer = Integer.MAX_VALUE;
    public int solution(String begin, String target, String[] words) {

        // words에 target이 있는지 확인
        boolean flag = false;
        for(String word : words) {
            if(word.equals(target)) {
                flag = true;
            }
        }
        // words에 target이 없으면 0 반환
        if(!flag) return 0;

        boolean[] visited = new boolean[words.length];
        // dfs 수행
        dfs(begin, target, 0, words, visited, begin);

        if(answer == Integer.MAX_VALUE) return 0;

        return answer;
    }

    private void dfs(String begin, String target, int depth, String[] words, boolean[] visited, String path) {
		
        // 이전에 찾은 depth보다 크면 탐색할 필요가 없음
        if(answer <= depth) return;
        
        // 첫 dfs에 begin과 target이 같으면 안됨
        if(depth != 0 && begin.equals(target)) {
            answer = Math.min(answer, depth);
            //System.out.println(path); // 탐색 경로를 볼 수 있다.
            return;
        }

        // words의 배열 갯수만큼 탐색
        for(int i = 0; i < words.length; i++) {
            // 다른 글자를 세기위한 카운트
            int count = 0;
            for(int k = 0; k < words[i].length(); k++) {
                // 해당 위치에 글자가 1개만 다르면
                // 나머지 글자는 위치가 같아야 한다. hot, hto는 다른 글자!!!!
                if (begin.charAt(k) != words[i].charAt(k)) {
                    count++;
                }
            }

            // 방문 이력이 없고, 글자 1개만 다르면
            if(!visited[i] && count == 1 && begin.length() == words[i].length()) {
                // 방문
                visited[i] = true;
                // dfs 수행
                dfs(words[i], target, depth + 1, words, visited, path +"->"+ words[i]);
                // 방문 이력 초기화
                visited[i] = false;
            }
        }
    }
}