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

- 문제 내용

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

코딩테스트 연습 - 단어 변환

---

- 문제 접근 방법

문제를 읽어보면 begin단어에서 target단어로 되기까지 과정이 탐색한 단어와 begin 단어는 한글자 빼고 모두 같은걸 알수 있다. 그리고 단어의 스펠링이 바뀔수 있는 모든 경우의수를 하나씩찾고 아니면 되돌아와서 다른 스펠링을 바꿔서 다시 찾고 해야한다. 그래서 해당문제는 백트래킹으로 접근하기로 했다.

 

1. 백트래킹 종료조건은 begin과 target이 같아졌을때이고, 그때까지 몇단계를 거쳐왔는지를 answer에 넣주면됨.

2. words에 있는 단어 하나를 뽑아 begin과 스펠링을 비교하기.

3. 비교후 다른 스펠이 하나 있다면 뽑은 단어를 begin에 넣고 다시 재귀호출

 

위의 생각으로 문제를 풀기로 했는데 2번에 비교조건을 어떻게 해결해야할지 몰라서 다른 블로그를 참고했다.

---

public 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 depth) {
    	if(begin.equals(target)) {
    		answer = depth;
    		return;
    	}
    	
    	for(int i=0; i<words.length; i++) {
    		if(check[i]) {continue;}
    		
    		int spell = 0; //같은 스펠링 개수
    		for(int j=0; j<begin.length(); j++) {
    			if(begin.charAt(j)==words[i].charAt(j)) {
    				spell++;
    			}
    		}
    		
    		if(begin.length()-1 == spell) { //이조건은 begin의 단어와 words의 단어가 한글자만
            					//다르다는말
    			check[i] = true;
    			dfs(words[i],target,words,depth+1); //begin을 words[i]로 갱신
                						//depth에 1증가(단계)
    			check[i] = false;
    		}
    	}
    }

---

- 마치며

위의 코드에서 본것처럼 백트래킹을 알고 있다면 단어를 바꿔주는 조건을 생각해내면 쉽게 풀수 있는 문제였다.

물론 나는 한시간정도 고민하다 다른 블로그를 참고 했는데 참고하고 나니 너무 아쉽게 다 풀지 못한 문제라고 생각한다. 이런문제는 수월하게 풀 수 있을정도로 공부하자!