프로그래머스 - 43163번: 단어 변환 [Java] (실패)

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

프로그래머스

1. 코드

import java.util.*;
class Solution {
    static int answer = Integer.MAX_VALUE;
    static boolean[] check;
    public int solution(String begin, String target, String[] words) {
        check = new boolean[words.length];
        dfs(begin, target, words, 0);
        return answer == Integer.MAX_VALUE ? 0 : answer;
    }
    
    public static void dfs(String begin, String target, String[] words, int cnt) {
        if (begin.equals(target)) {
            answer = Math.min(answer, cnt);
            return;
        }

        for (int i = 0; i < words.length; i++) {
            if (!check[i] && canTransform(begin, words[i])) {
                check[i] = true;
                dfs(words[i], target, words, cnt + 1);
                check[i] = false;
            }
        }
    }
    
    public static boolean canTransform(String word1, String word2) {
        int diffCount = 0;
        for (int i = 0; i < word1.length(); i++) {
            if (word1.charAt(i) != word2.charAt(i)) {
                diffCount++;
                if (diffCount > 1) {
                    return false;
                }
            }
        }
        return diffCount == 1;
    }
}

2. 설명

static int answer = Integer.MAX_VALUE;
static boolean[] check;
public int solution(String begin, String target, String[] words) {
    check = new boolean[words.length];
    dfs(begin, target, words, 0);
    return answer == Integer.MAX_VALUE ? 0 : answer;
}

answer의 값이 Integer.MAX_VALUE 값이 아니라면 begin의 문자가 target이 되지 않았다는 것을 의미하기에 0을 반환하며 아니라면 answer를 반환합니다.

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

    for (int i = 0; i < words.length; i++) {
        if (!check[i] && canTransform(begin, words[i])) {
            check[i] = true;
            dfs(words[i], target, words, cnt + 1);
            check[i] = false;
        }
    }
}

dfs 함수에서는 깊이 우선 탐색을 진행하는데 begin의 값과 target이 동일하다면 종료하는데 answer의 값보다 cnt의 값이 적다면 cnt의 값을 저장합니다.

반복문을 통해서 배열의 다른 인덱스 값에 접근하는데 check를 이용하여 방문 여부를 저장합니다.

public static boolean canTransform(String word1, String word2) {
    int diffCount = 0;
    for (int i = 0; i < word1.length(); i++) {
        if (word1.charAt(i) != word2.charAt(i)) {
            diffCount++;
            if (diffCount > 1) {
                return false;
            }
        }
    }
    return diffCount == 1;
}

canTransform은 word1과 word2의 문자의 비교 결과 1개만 차이가 나면 true를 아니라면 false를 반환하는 함수입니다. 따라서 check의 값이 false 즉, 방문하지 않은 배열의 인덱스에서 begin과 words[i]의 문자 비교 시 1개만 차이가 날 경우 반복됩니다.

3. 정리

• 문제에 대한 이해가 부족했다.
• begin과 word에서 문자 비교 시 1개의 문자만 다르면 진행하는 방식으로 진행된다.

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges