[프로그래머스]DFS:단어변환(java)

문제보러가기

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

이문제의 포인트는 주어진 단어의 한글자만 바꾼 단어가 주어진 단어의 집합에 있는지 확인하면서 진행해 나가는 과정이었다! 처음에는 단어를 바꾸니까 subString()을 쓰면 되겠다! 했는데 더 복잡해졌다는,,,,

 

 

 

문제풀이

-주어진 단어집합에 내가 비교하는 단어에서 한글자만 다른단어가 있는지 탐색

-visited == false라면 dfs에 그 단어로 다시 dfs진행

-target과 같아질때까지 비교

 

 

나는 한글자만 다른단어가 있는지 탐색하는 부분을 따로 checkWord라는 함수로 빼서 사용하였다.

 

public class Solution {

	static int minCnt = Integer.MAX_VALUE;
	public static void main(String[] args) {
		
		String begin = "hit"; 
		String target ="cog"; 
		String[] words ={"hot", "dot", "dog", "lot", "log"};
		
		dfs(new boolean[words.length],0,begin,target,words);
        //해당 단어가 없을경우 0을 출력
		if(minCnt==Integer.MAX_VALUE)
			minCnt=0;
		System.out.println(minCnt);
		
		
	}
	public static void dfs(boolean[] visited,int cnt,String begin,String target,String[] words){
		
        //target과 일치하면 minCnt갱신해주기
		if(begin.equals(target)){
			if(minCnt>cnt)
				minCnt=cnt;
			return;
		}
		
        //단어집합에 존재하는 단어일 경우 dfs
		for(int i=0;i<words.length;i++){
			if(!visited[i] && checkWords(begin,words[i])){
				visited[i]=true;
				dfs(visited,cnt+1,words[i],target,words);
				visited[i]=false;
			}
		}	
		
	}
	//한글자만 바꾸는지 체크
	public static boolean checkWords(String begin,String target){
		
		char[] c1 = begin.toCharArray();
		char[] c2 = target.toCharArray();
		
		int change=0;
		for(int i=0;i<c1.length;i++){
			if(c1[i]!=c2[i]) change++;
		}
		if(change==1) return true;
		
		return false;
	}

}