프로그래머스 Lv3 단어변환(DFS/BFS) Java

문제 설명

두 개의 단어 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 합니다.

 

출처: <https://programmers.co.kr/learn/courses/30/lessons/43163>

 

##문제이해##

처음에는 단어 하나만 바꿀 수 있다는걸 다르게 이해해서..접근방법이 틀렸었다.

모든단어들이 아니라 특정단어들만 dfs의 조건이된다.

1. Hit-> hot 밖에 바꿀수없음. Ht2글자가 같은게 딱1개.
2. Hot->dot,lot 2개의 단어가 한글자씩 다름.
3. 글자 비교를 할때 유의점이 존재함!!

Contains으로 비교를 했더니 실패하는 케이스가 존재함.. 위치마저 동일해야 하기때문에 포함여부로 체크하는건 안맞았다!

 

##프로그래머스 제출한코드##

class Solution {
    static boolean[] visit;
    static int result=100;
    public int solution(String begin, String target, String[] words) {
        boolean check = false; //target단어 포함여부 확인
    	//단어갯수만큼 방문여부 체크가능한 boolean배열 생성
        visit= new boolean[words.length]; 
    	//words에 target단어가 있는지 체크하고 있는경우 dfs를 수행
    	for(String word: words) {
    		if(word.equals(target)) check=true;
    	}
    	if(check) {
    		dfs(0,begin,words,target);
    	}else{
            result=0;
        }
        return result;
    }
    
    public static void dfs(int depth,String answer,String[] words,String target){
    	//종료조건
    	if(target.equals(answer)) {
    		result= Math.min(depth,result);
    		return;
    	}
    	//수행
    	for(int i=0; i<words.length; i++) {
    		//동일한 단어를 2개 가지고 있는지 체크
    		int cnt=0;
    		if(visit[i]==false) {
    			String str = words[i];
    			for(int j=0;j<str.length();j++) {
    				char ch1 = str.charAt(j);
    				char ch2 = answer.charAt(j);
    				if(ch1==ch2) {
    					cnt++;
    				}
    			}
    		}
    		
    		//방문여부 체크
    		if(visit[i]==false && cnt==2) {
    			visit[i]=true;//방문처리
    			dfs(depth+1,words[i],words,target);
    			visit[i]=false;
    			
    		}
    		
    	}
    	
    }
}

테스트 케이스를 다 통과하지 못했다 ㅠㅠ 3번 케이스에 도움적어주신분들이 말한부분이 동일한 단어 중복이나 위치에따른char비교를 말 했었는데.. 안된다

##다른 설명잘되어있는 블로그에서 성공한 코드##

https://velog.io/@hammii/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%8B%A8%EC%96%B4-%EB%B3%80%ED%99%98-java

나중에 비교해봐야겠다..어느부분이 다른지

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

        dfs(begin, target, words, 0);
        return answer;
    }
    
    public static void dfs(String begin, String target, String[] words, int cnt) {
        if (begin.equals(target)) {
            answer = cnt;
            return;
        }

        for (int i = 0; i < words.length; i++) {
            if (visited[i]) {
                continue;
            }

            int k = 0;    // 같은 스펠링 몇개인지 세기
            for (int j = 0; j < begin.length(); j++) {
                if (begin.charAt(j) == words[i].charAt(j)) {
                    k++;
                }
            }

            if (k == begin.length() - 1) {  // 한글자 빼고 모두 같은 경우
                visited[i] = true;
                dfs(words[i], target, words, cnt + 1);
                visited[i] = false;
            }
        }
    }
}

##Spring에서 테스트하던 코드##

public class WordConversion {
    static String begin="hit"; 
    static String target = "cog";
    static String[] words={"hot", "dot", "dog", "lot", "log", "cog"};
    static boolean[] visit;
    static int result=100;
    public static void main(String[] args) {
    	boolean check = false; //target단어 포함여부 확인
    	visit= new boolean[words.length]; //단어갯수만큼 방문여부 체크가능한 boolean배열 생성
    	//words에 target단어가 있는지 체크하고 있는경우 dfs를 수행
    	for(String word: words) {
    		if(word.equals(target)) check=true;
    	}
    	if(check) {
    		dfs(0,begin);
    	}else{
            result=0;
        }
    	
    	System.out.println(result);
    	
    }
    
    public static void dfs(int depth,String answer){
    	//종료조건
    	if(target.equals(answer)) {
    		result= Math.min(depth,result);
    		return;
    	}
    	//수행
    	for(int i=0; i<words.length; i++) {
    		//동일한 단어를 2개 가지고 있는지 체크
    		int cnt=0;
    		if(visit[i]==false) {
    			String str = words[i];
    			for(int j=0;j<str.length();j++) {
    				char ch1 = str.charAt(j);
    				char ch2 = answer.charAt(j);
    				if(ch1==ch2) {
    					cnt++;
    				}
    			}
				/*
				 * for(int j=0;j<str.length();j++) { char ch = str.charAt(j);
				 * if(answer.contains(String.valueOf(ch))) { cnt++; } }
				 */    		}
    		
    		//방문여부 체크
    		if(visit[i]==false && cnt==2) {
    			visit[i]=true;//방문처리
    			dfs(depth+1,words[i]);
    			visit[i]=false;
    			
    		}
    		
    	}
    	
    }
}