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

문제

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

프로그래머스

설명

입출력

나의 풀이

문제의 첫 번째 예시를 보면 

begin에서 target으로 가기 위한 최소 단계는 아래와 같이 4번을 거쳐서 4를 리턴하게 된다. 

최소 단계가 아닌 경우들 중 하나의 예시는 아래와 같이 6번을 거치게 된다. 

문제를 풀기 전에 우선 계획을 세웠다. 

1. 한 단어의 한 단어마다 dfs를 돌리기.

("hit"의 경우에는 h (index=0), i (index=1), t (index=2)를 기준으로 index를 dfs에 넣어주기)

- dfs의 구조

dfs(단어의 index, 방문할 단어(word) , target, words, visited)

visited를 생성한 이유는 확인했던 단어를 다시 한번 확인하면 결국 전에 했던 과정을 반복하게 된다고 생각함.)

2. dfs에 들어온 단어가 target과 같다면 return 하기.

3. dfs에서의 과정

- 들어온 단어가 target과 같은지 확인

- 들어온 단어의 index를 기준으로 if 조건문을 만들기

  (1) index == 0 일 때(단어의 첫 번째 index가 들어왔을 때) : word.substring(1) -> "hit"의 경우 "it"로 비교

  (2) index == target.length() 일 때 (단어의 마지막 index가 들어왔을 때) : word.substring(0, target.length()-1)

       -> "hit"의 경우 "hi"로 비교

  (3) 위의 (1), (2)를 제외한 중간 index가 들어왔을 때 : word.substring(0, index) + word.substring(index+1)

       -> "hit"의 경우 "ht"로 비교

- 위의 조건문에서 index에 따라 for 반복문을 돌며 words 배열 속 단어들을 substring 해서 

   한 개의 알파벳씩만을 바꾸면서 dfs를 돌리기.

- count 변수로 이동한 단계를 표현하고 target과 같을 때마다 더 작은 것을 result변수에 갱신해 주기.

 

위의 계획을 바탕으로 코드를 구현했다. 

import java.util.*;

class success_clean {

    static int result = 50;
    static int count = 0;

    public int solution(String begin, String target, String[] words) {
        int answer = 0;

        int begin_size = begin.length();
        boolean[] visited = new boolean[words.length];

        for(int i=0; i < begin_size; i++) {
            dfs(i,begin,target,words,visited);
        }

        if(result == 50) {
            return 0;
        } else {
            return result;
        }
    }

    static public void dfs(int index, String word, String target, String[] words, boolean[] visited) {
        if(word.equals(target)) {
            result = Math.min(result,count);
            return;
        }

        if (index == 0) {
            String index_first = word.substring(1);
            for(int i=0; i < words.length; i++) {
                if(words[i].substring(1).equals(index_first) && !visited[i]) {
                    count++;
                    visited[i] = true;
                    for(int j=0; j < target.length(); j++) {
                        dfs(j,words[i],target,words,visited);
                        if(words[i].equals(target)) {
                            visited[i] = false;
                            count--;
                            return;
                        }
                    }
                    visited[i]=false;
                }
            }
        } else if (index == target.length()-1) {
            String index_last = word.substring(0,target.length()-1);
            for(int i=0; i < words.length; i++) {
                if (words[i].substring(0,target.length()-1).equals(index_last) && !visited[i]) {
                    count++;
                    visited[i] = true;
                    for(int j=0; j < target.length(); j++) {
                        dfs(j,words[i],target,words,visited);
                        if(words[i].equals(target)) {
                            visited[i] = false;
                            count--;
                            return;
                        }
                    }
                    visited[i]=false;
                }
            }
            count--;
        } else {
            String index_middle = word.substring(0,index) + word.substring(index+1);
            for(int i=0; i < words.length; i++) {
                if ((words[i].substring(0,index) + words[i].substring(index+1)).equals(index_middle) && !visited[i]) {
                    count++;
                    visited[i] = true;
                    for(int j=0; j < target.length(); j++) {
                        dfs(j,words[i],target,words,visited);
                        if(words[i].equals(target)) {
                            visited[i] = false;
                            count--;
                            return;
                        }
                    }
                    visited[i]=false;
                }
            }
        }
    }
}

감동의 순간..

dfs 유형의 문제를 풀며 target과 다르면 방문을 취소하고 되돌아가는 패턴을 이해하기 어려워서 이 부분을 구현하는 게 힘들었다.

처음에 그럴듯하게 풀어놓고 100번 정도의 삽질 끝에 완성해 냈다...

알고 보니 count 변화, visited 변환, return 등을 아무 데나 질러놓고 좋다고 실행한 거였다..ㅠㅠ

그래도 못 풀 것만 같았던 dfs 3단계 문제를 풀다니 상당히 감격스럽답🫢