[프로그래머스]Lv.3 단어 변환

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

프로그래머스

---

문제

• 두 개의 단어 begin, target과 단어의 집합 words가 있습니다.
• 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
  • 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
  • 2. words에 있는 단어로만 변환할 수 있습니다.
• 예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.
• 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예제

설계과정

1. begin에서 target 으로 바꾸기 위해 words[ ] 배열에서 각 문자별로 몇 개의 스펠링을 바꿔야하는지 확인한다.

• hot > cog 로 가기 위해서 words 배열에 첫 번째 원소인 dot 와 비교한다.
• hot와 dot는 스펠링 1개가 차이난다.
• hot와 dog는 스펠링 2개가 차이난다.
• 이처럼 words[ ] 배열과 전부 비교한다. 

2. begin 문자와 words[ i ] 번째 단어가 스펠링이 1개만 다르다면 ch[ ] 배열에 방문여부를 넣어주고 재귀함수를 호출한다.

 

3. 재귀함수를 호출하면서 cnt 변수에 1씩 더해준다.

 

4. 결과를 출력한다.

 

아래 블로그 글을 참조했다.

https://jisunshine.tistory.com/157

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

---

풀이과정

1. begin과 words[ ] 배열에 있는 각 문자들을 하나씩 비교하면서 스펠링이 몇개가 다른지 확인한다.

• 가독성을 위해 따로 메소드를 빼서 만들었다.
• start는 begin 값이, end는 words[i] 값이 들어간다.

2. 다른 스펠링이 1개라면 ch[ ] 배열에 값을 true로 변경하고 재귀함수를 호출한다.

• 스펠링이 1개라면 이미 방문을 했다는 의미이기에 해당 위치에 방문 여부를 의미하는 ch[ ] 배열 값을 true로 저장한다.
• 이미 방문을 했기에 cnt는 1로, i 번째 배열 원소에 대한 것이기에 i 를, 그리고 계산에 필요한 target과 words 를 파라미터로 넣어서 재귀함수를 호출한다. 

3. target 과 words[cur] 가 동일하면 answer에 cnt를 넣고 그대로 리턴한다.

• 현재 words[ ] 배열에 문자와 target가 동일하면 원하는 결과를 찾은 것이기에 그동안 누적된 cnt를 결과 변수 answer에 넣고 리턴한다.

4. 그게 아니라면 words 배열의 크기만큼 for문을 돌면서 방문하지 않았고, 스펠링이 1개만 다른 값들을 찾아 재귀함수를 반복해서 호출한다.

 

5. answer 를 리턴한다.

---

답안소스

• 프로그래머스

class Solution {
    static boolean[] ch;
	static int answer = 0;
    
    public int solution(String begin, String target, String[] words) {

        for(int i=0; i<words.length; i++) {
			if(compare(begin, words[i]) <= 1) {
				ch = new boolean[words.length];
				ch[i] = true;
				DFS(1, i, target, words);
			}
		}
        
        return answer;
    }
    
    static void DFS(int cnt, int cur, String target, String[] words) {
		
		if(target.equals(words[cur])) {
			answer = cnt;
			return;
		}else {
			for(int i=0; i<words.length; i++) {
				if(!ch[i] && compare(words[cur], words[i]) == 1) {
					ch[i] = true;
					DFS(cnt + 1, i, target, words);
					ch[i] = false;
                }
            }
        }
    }

    static int compare(String begin, String target) {
        int n = 0;

        for(int i=0; i<target.length(); i++) {
            if(begin.charAt(i) != target.charAt(i)) {
                n++;
            }
        }

        return n;
    }
}

---

• 이클립스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static boolean[] ch;
	static int answer = 0;

	public void DFS(int cnt, int cur, String target, String[] words) {
		
		if(target.equals(words[cur])) {
			answer = cnt;
			return;
		}else {
			for(int i=0; i<words.length; i++) {
				if(!ch[i] && compare(words[cur], words[i]) == 1) {
					ch[i] = true;
					DFS(cnt + 1, i, target, words);
					ch[i] = false;
				}
			}
		}
	}
	
	public static int compare(String start, String end) {
		int n = 0;
		
		for(int i=0; i<end.length(); i++) {
			if(start.charAt(i) != end.charAt(i)) {
				n++;
			}
		}
		
		return n;
	}
	
	public static void main(String[] args) throws IOException {
		Main word = new Main();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		String begin = st.nextToken();
		String target = st.nextToken();
		
		String[] words = new String[]{"hot", "dot", "dog", "lot", "log", "cog"};
		
		for(int i=0; i<words.length; i++) {
			if(compare(begin, words[i]) <= 1) {
				ch = new boolean[words.length];
				ch[i] = true;
				word.DFS(1, i, target, words);
			}
		}
		
		System.out.println(answer);
	}
}