코딩 테스트를 치면서 실무에서 자주 사용하는 해쉬, 문자열 관련 문제들은 비교적 수월하게 풀었지만, 내가 실무에서 자주 사용할 일이 없는 탐색이나 그래프 문제가 나오면 항상 고전을 하였다.
그렇기에 내가 약했던 유형을 위주로 문제를 풀어보며 정리를 해보려고 한다.

오늘 정리할 코딩 테스트 문제는 프로그래머스의 '단어 변환' 문제로 dfs를 활용해 풀 수 있는 레벨 3 문제였다.
개인적으로 재귀함수를 효과적으로 사용할 수 있다면 어렵지 않게 풀 수 있는 문제였다고 생각한다.

문제

풀이 코드

class Solution {
    static boolean[] check;
    static int answer = 0; 
    public int solution(String begin, String target, String[] words) {
        check = new boolean[words.length];
        dfs(begin, target, words, 0);
        return answer;
    }
    public void dfs(String begin, String target, String[] words, int count){
        if(begin.equals(target)){
            answer=count;
            return;
        }
        for(int i=0; i<words.length; i++){
            if(check[i] == true){
                continue;
            }
            int same = 0;
            for(int j=0; j<begin.length(); j++){
                if(begin.charAt(j) == words[i].charAt(j)){
                    same++;
                }
            }
            if(same == begin.length()-1){
                check[i] = true;
                dfs(words[i], target, words, count+1);
                check[i]  = false;
            }
        }
    }
}

문제 풀이

1. begin, target, words 그리고 현재 몇번째 단어 변환이 이루어젔는지 확인할 int count를 받는 void 함수 dfs를 생성해준다.
2. 재귀함수로 활용할 것이기 떄문에 탈출 조건으로 begin이 target과 같은 값이 될때 탈출하게 하고, 이때 answer 값을 변수로 받은 count 값으로 설정해준다. 이를 위해선 answer을 클래스 안에서 static 값으로 지정해준다.
3. 클래스 내부에 static 값으로 boolean array인 check을 지정해주고 solution 메써드 안에서 words의 길이만큼이라고 지정해준다.
4. dfs 메써드 안에서 words의 길이만큼 순회하는 반복문을 만들어 해당 인덱스에 있는 check 값이 true일 경우 이미 방문을 했던 것이기 때문에 지나치고, 그 이외의 경우 charAt을 활용해 begin과 words[i] 값의 글자 갯수가 몇개나 일치하는지 확인한다.
5. 일치하는 글자 수가 문제에서 요구하는 '한개 빼고 전부 일치' 일 경우 check에서 해당 배열의 인덱스 값을 true로 설정한다.
6. words[i] 값을 begin값으로 설정하고 count를 1 증가시킨 값을 재귀로 호출한다.
7. 모든 경우의 수를 전부 보기 위해서 check[i] 값은 false로 설정한다.

느낀점

마지막 7번 값을 설정하는 것을 깜빡하고 왜 정상적인 값이 나오지 않는지 고민을 했었다.
아직 까지도 dfs 문제가 문자열 유형의 문제처럼 자유롭게 머릿속에서 그려지지는 않지만, 해당 유형의 문제를 지속적으로 풀어봐서 자연스러워지게 만들어야 할 것 같다.