프로그래머스 단어변환

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

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

 

 

풀이 :

① DFS를 이용핸 도달할 수 있는 모든 경로를 탐색. 

② 탐색 한 경로의 최소값을 출력

 

2021.09.19 - [알고리즘/알고리즘] - 깊이 우선 탐색 Depth-first search

깊이 우선 탐색 Depth-first search

 

구현 JAVA

import java.util.*;
class Solution {
    static String target;
	static int answer  = Integer.MAX_VALUE;
    public int solution(String begin, String target, String[] words) {
        
    	boolean[] visited = new boolean[words.length];
    	this.target = target;

		dfs(words, visited, begin, 0);

    	return answer == Integer.MAX_VALUE ? 0 : answer;
    }
    

	public void dfs(String[] words, boolean[] visited, String word, int distance) {
    	
    	if(word.equals(target)) {  
    		answer = Math.min(distance, answer);
        	return ;
    	}
    	
    	for(int i = 0; i<words.length; i++) {    		
    		if(!visited[i] && checkConvert(word, words[i])) {
				visited[i] = true;
				dfs(words, visited, words[i], distance+1);
				visited[i] = false;
    		}
    	}
    }


	private boolean checkConvert(String word1, String word2) {
		char[] arr1 =  word1.toCharArray();
		char[] arr2 =  word2.toCharArray();
		
		int differentCount = 0;
		
		for(int i = 0; i<arr1.length; i++) {
			if(arr1[i] != arr2[i]) {
				differentCount++;
			}
		}
		
		return differentCount == 1 ? true : false;
	}
}