[Programmers] 단어 변환 - 깊이/너비 우선 탐색(DFS/BFS)

// 단어 변환 - 깊이/너비 우선 탐색(DFS/BFS)
public class WordConversion {
	public int solution(String begin, String target, String[] words) {
		int answer = dfs(begin, target, words, new boolean[words.length], Integer.MAX_VALUE, 0);
        return answer == Integer.MAX_VALUE ? 0 : answer + 1; // target이 words[]에 존재하지 않으면 0 반환
	}

	private int dfs(String begin, String target, String[] words, boolean[] visit, int min, int cnt) { // cnt : words[] 내에서 이동하는 횟 수
		for (int i = 0; i < words.length; i++) {
			if (!visit[i] && compare(begin, words[i])) {
				if (words[i].equals(target)) {
					return cnt;
				}
				visit[i] = true;
				min = dfs(words[i], target, words, visit, min, cnt + 1);
			}
		}
		return min;
	}

	private boolean compare(String str1, String str2) {
		int cnt = 0;
		for (int i = 0; i < str1.length(); i++) {
			if (str1.charAt(i) != str2.charAt(i)) {
				cnt++;
			}
		}
		return cnt <= 1; // cnt == 0 : str1-str2 동일, cnt == 1 : str1-str2 한 글자 차이 => 두 상황 모두 true로 리턴
	}
}