[프로그래머스/JAVA] 단어 변환

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

프로그래머스

---

- 문제 풀이

1. visited 배열과 answer 변수를 초기화.
2. dfs 함수를 통해 재귀적으로 변환 과정을 탐색.
3. 한 글자 차이가 나는 단어로만 변환을 시도.
4. 모든 경로를 탐색하면서 목표 단어에 도달하면 cnt 값을 answer에 저장.
5. 탐색 완료 후 최종 변환 횟수를 반환.

 

1. 변수 초기화:

• visited: 각 단어가 변환 과정에서 이미 사용되었는지 확인하기 위한 배열입니다. 길이는 주어진 words 배열의 길이와 동일하게 설정됩니다. 모든 값은 처음에 false로 설정되어, 아직 단어들이 변환에 사용되지 않았음을 나타냅니다.
• answer: 변환 과정에서 최소 몇 단계가 필요한지를 기록하는 변수입니다. 시작은 0으로 초기화됩니다.

class Solution {
    static int answer = 0;
    static boolean[] visited;

 

 

 

 

2. DFS 탐색 함수 (dfs) 정의:

• 이 함수는 주어진 시작 단어 begin에서 목표 단어 target으로 가는 변환 경로를 재귀적으로 탐색하는 역할을 합니다.

public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];

        dfs(begin, target, words, 0);

        return answer;
    }

 

 

 

 

DFS 함수 단계별 설명

 

3. 기저 조건 확인:

• 함수가 호출되면 먼저 begin과 target이 같은지 확인합니다.
• 만약 두 단어가 같다면, 변환이 완료된 것이므로 answer에 현재까지의 변환 단계 수인 cnt를 저장하고 함수를 종료합니다. 즉, 목표 단어에 도달했으니 더 이상 탐색할 필요가 없다는 의미입니다.

public static void dfs(String begin, String target, String[] words, int cnt){
        if(begin.equals(target)) {
            answer = cnt;
            return;
        }

 

 

 

 

4. 변환 가능한 단어 찾기:

• 현재 단어에서 변환할 수 있는 단어를 찾기 위해, words 배열을 순회합니다.
• 이미 방문한 단어는 visited[i]가 true이므로 이를 건너뛰고 다음 단어로 넘어갑니다.

 for(int i = 0; i < words.length; i++) {
            // 이미 방문한 단어는 visited[i]가 true이므로 이를 건너뛰고 다음 단어로 넘어감
            if(visited[i]) {
                continue;
            }

 

 

 

5. 한 글자 차이 확인:

• 현재 begin 단어와 words[i] 단어가 얼마나 다른지를 확인합니다. 이때, 두 단어가 정확히 한 글자만 다를 경우에만 다음 변환 대상으로 선택할 수 있습니다.
• k라는 변수를 사용하여 두 단어의 각 글자를 비교하고, 동일한 글자의 개수를 셉니다. 두 단어가 한 글자만 다를 경우에는 k 값이 begin.length() - 1과 같아야 합니다.

// 현재 단어(begin)와 words[i]가 몇글자가 같은지 체크
            int k = 0;
            for (int j = 0; j < begin.length(); j++) {
                if(begin.charAt(j) == words[i].charAt(j)) {
                    k++;
                }
            }

            // 글자가 딱 한글자만 다른 경우
            // hit -> hot
            if(k == begin.length() - 1) {

 

 

 

6. 재귀 호출 (변환 후 다음 단계로):

• 변환할 수 있는 단어를 찾았다면, 해당 단어로 변환하고 dfs를 재귀적으로 호출합니다.
• 변환 후에는 그 단어가 이미 사용되었음을 표시하기 위해 visited[i] = true로 설정하고, 변환 횟수를 증가시켜 cnt + 1을 인자로 전달합니다.

// 글자가 딱 한글자만 다른 경우
            // hit -> hot
            if(k == begin.length() - 1) {
                visited[i] = true;
                dfs(words[i], target, words, cnt + 1);

 

 

 

 

 

7. 다른 경로 탐색을 위한 방문 표시 해제:

• 모든 경로를 탐색하려면, 변환이 끝난 후에는 다시 그 단어에 대한 방문 표시를 false로 해제해 줍니다. 이렇게 해야 다른 경로에서도 그 단어를 사용할 수 있습니다.
• 예를 들어, hit -> hot -> dot -> cog 경로 외에도 hit -> hot -> lot -> log -> cog와 같은 경로도 탐색해야 하므로, 방문 표시를 해제해서 다른 경로에서 해당 단어를 재사용할 수 있도록 합니다.

// 글자가 딱 한글자만 다른 경우
            // hit -> hot
            if(k == begin.length() - 1) {
                visited[i] = true;
                dfs(words[i], target, words, cnt + 1);
                visited[i] = false; // 다른 경로 탐색 위해 방문표시 해재
            }
        }

 

 

 

---

 

 

 

- 정답 코드

class Solution {
    // 각 단어가 변환과정에서 사용되었는지 여부 판단
    static boolean[] visited;
    // 몇 단계만에 변환 가능한지 저장
    static int answer = 0;


    // 현재 단어(begin)에서 target으로 가는 변환 과정을 재귀적으로 탐색
    public static void dfs(String begin, String target, String[] words, int cnt){
        if(begin.equals(target)) {
            answer = cnt;
            return;
        }

        for(int i = 0; i < words.length; i++) {
            // 이미 방문한 단어는 visited[i]가 true이므로 이를 건너뛰고 다음 단어로 넘어감
            if(visited[i]) {
                continue;
            }

            // 현재 단어(begin)와 words[i]가 몇글자가 같은지 체크
            int k = 0;
            for (int j = 0; j < begin.length(); j++) {
                if(begin.charAt(j) == words[i].charAt(j)) {
                    k++;
                }
            }

            // 글자가 딱 한글자만 다른 경우
            // hit -> hot
            if(k == begin.length() - 1) {
                visited[i] = true;
                dfs(words[i], target, words, cnt + 1);
                visited[i] = false; // 다른 경로 탐색 위해 방문표시 해재
//만약 hit -> hot -> dot -> cog로 변환하는 경로가 있다고 할 때,
// 다른 경로인 hit -> hot -> lot -> log -> cog도 탐색하려면,
// 이미 방문한 단어들을 다시 탐색할 수 있도록 방문 표시를 해제해야 함
            }
        }


    }

    public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];

        dfs(begin, target, words, 0);

        return answer;
    }
}