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

• 단어 변환

문제 설명

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

입출력 예begintargetwordsreturn

"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

import java.util.*;

class Solution {
   static HashMap<String,Boolean>check;
    
    private int bfs(String begin, String target, String[] words){
        Queue<String> queue = new LinkedList<>();   //큐 선언
        queue.add(begin);   //큐에 첫 문자열 담기
        check.put(begin,true); //첫 문자열 방문 처리
        int answer=0;
        while(!queue.isEmpty()){
            String s = queue.poll();
            ArrayList<String> checkStr = findStr(s,words);
            
            System.out.println("Hello Java s "+s);
            System.out.println("Hello Java checkStr "+checkStr);
            //찾을 수 있는 단어 중 타겟에서 한단어 차이나는게 존재하면 바로 해당 단어로 변환해주기
            int value = 0;
            String tagetTmp = "";
            for(int i=0; i<checkStr.size(); i++){
                if(!check.get(checkStr.get(i))){    //방문하지 않은 단어일때
                    value = findTarget(checkStr.get(i),target);
                }
                if(value==1){
                    tagetTmp = checkStr.get(i);
                }
            }
            System.out.println("Hello Java tagetTmp "+tagetTmp);
            System.out.println("Hello Java value "+value);
            for(int i=0; i<checkStr.size(); i++){
                if(!check.get(checkStr.get(i))){    //방문하지 않은 단어일 
                    check.put(checkStr.get(i),true);    //우선 방문체크
                    if(value==0){
                        queue.add(checkStr.get(i));
                    } else if(value==1) {
                        //바로 이동할 수 있는 경우
                        queue.poll();
                        queue.add(tagetTmp);
                    }
                }
            }
            System.out.println("Hello Java answer "+queue.toString());
            answer++;
            for (String q:queue) {
                if (q.equals(target)) return answer;
            }
        }
        return 0;
    }
    private int findTarget(String str, String target){
        int val = 0;
        for(int i=0; i<str.length(); i++){
            if(str.charAt(i)!=target.charAt(i)){      //같지 않을 경우
                val++;
            }
        }
        if(val==1){
            return 1;
        }
        return 0;
    }
    
    private ArrayList<String> findStr(String str, String[] words){
        ArrayList<String> list = new ArrayList<>();
        String[] tmp = str.split(""); //비교대상 문자열
          
        for(String word : words){
            String[] wordTmp = word.split("");    //비교할 문자열
            int val = 0;
            
            for(int i=0; i<wordTmp.length; i++){
                if(!wordTmp[i].equals(tmp[i])){      //같지 않을 경우
                    val++;
                }
            }
            if(val==1){
                if(!check.get(word)){    //방문하지 않은 단어일 경우
                    list.add(word); //하나만 같을 경우 변경 가능
                }
            }
        }
        return list;
    }
    
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        check=new HashMap<String,Boolean>();
        for(String tmp : words){
            //System.out.println("Hello Java answer "+tmp);
            check.put(tmp,false);
        }
        answer = bfs(begin,target,words);
        
        return answer;
    }
}

bfs/dfs를 활용해서 푸는 문제

테스트케이스 1번이 통과가 안되는데 문제는 정답으로 처리되는 문제가 발생해서

여기저기 뜯어고쳐봄 테스트케이스는 전부 통과하고 정답처리까지 받았으나

다른 케이스를 추가했더니 또 안되는 상황이 발생함

문제가 이상한건지 확인 필요..