[자바] 프로그래머스 단어 변환

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

프로그래머스

 

이 문제는 단순히 탐색만 하는 것이 아니라 조건에 맞는 경우에 대한 탐색을 하는 문제였다.

 

문제를 풀다가 막힌 부분이 여러 군데 있었는데...

1. 조건을 어디에 넣어야 하는가..

2. visited를 boolean으로 선언해야하는가? int로 선언하면서 동일한 경우에 대한 인덱스에 해당하는 visitied[idx]값을 출력해야하는가?

3. 하나의 값만 차이날 때 dfs를 실행해야 되는데 어떻게 구현할까

4. answer는 언제 값을 갱신해야되지?

이 정도가 있었던 것 같다. 

 

1번의 경우, 조건은 dfs에 넣고, main 함수에서는 단순히 dfs를 호출하기만 하는 방식으로 구현했다.

2번의 경우, boolean으로 했는데 결론적으로 내가 작성한 방법은 틀렸지만 cnt로 따로 값을 세어가면서 만약 begin과 target이 같아지는 순간의 cnt를 answer에 넣으면 된다.

3번의 경우, check라는 변수를 통해 동일한 경우에 대해서 check 변수에 값을 추가해줬고, 만약 그렇게 만들어진 check 변수가 words[0].length()랑 1 차이가 난다면 하나를 제외하고는 다 동일한 단어라는 걸 알 수 있게 된다.

4번의 경우, begin과 target이 같아지는 순간의 cnt 값을 answer에 넣어주면 된다.

 

뭔가 조금만 더 생각했으면 풀 수 있었을 것 같은데 혼자 힘으로 다 풀어내지 못해서 너무 아쉽다.

다음에 다시 풀어보자!

import java.util.*;

class Solution {
    public static boolean[] visited;
    public static int answer = 0;
    public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];
        dfs(begin, target, words, 0);
        return answer;
    }
    
    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++){
            if(visited[i]) continue;
            
            int check=0;
            for(int j = 0; j < words[i].length(); j++){
                if(begin.charAt(j) == words[i].charAt(j)){
                    check++;
                }
                if(check == begin.length()-1){
                    visited[i] = true;
                    dfs(words[i], target, words, cnt+1);
                    visited[i] = false;
                }
            }
        }
    }
}