[DFS/BFS] 단어변환 - Java코드 ★★

https://programmers.co.kr/learn/courses/30/lessons/43163?language=java 

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

 

 

 

문제

 

 

 

설계

DFS / BFS 을 통해 결과를 구하는 로직은 어렵지 않지만,

여러가지 클래스와 인터페이스의 존재를 알고 사용하는것이,

간결하면서도 효율적인 코드를 만들 수 있다고 생각되므로

Stream() 클래스에 대해서 좀더 공부해야할것같다.

 

풀이

import java.util.ArrayList;
import java.util.Arrays;
class Solution {
    static int answer=50;
    public static boolean compareString(String str1, String str2) {
        int cnt = 0;
        for (int i = 0; i < str1.length() && cnt < 2; i++) 
            if (str1.charAt(i) != str2.charAt(i)) 
                cnt++;       
        return cnt == 1;
    }
    public static void dfs(String begin, String target, ArrayList<String> list,int cnt) {
        if(begin.equals(target)) {
            answer = Math.min(answer, cnt);
            return;
        }
        for(int i=0;i<list.size();i++) {
            if(compareString(begin, list.get(i))) {
                String str = list.get(i);
                list.remove(i);
                dfs(str, target, list,cnt+1);
                list.add(i,str);
            }
        }

    }   
    public static int solution(String begin, String target, String[] words) {
        // 포함하지 않는 경우 0 반환후 종료
        //if(!Arrays.stream(words).anyMatch(i -> i == target))
		//	return 0;
        boolean flag=false;
        for(String s : words) {
            if(s.equals(target)){
                flag = true;
                break;
            }
        }
        if(!flag)   return 0;
        ArrayList<String> list = new ArrayList<String>(Arrays.asList(words));
        dfs(begin,target,list,0);
        return answer;
    }
}

 

문자열을 비교하면서 다른 문자의 갯수가 1개인 경우 true를 반환하도록 CompareString() 함수 구현

dfs함수는 begin, target이 같아지는 시점에 종료문을 넣고, 재귀호출되면서 모든 경우를 돌도록 구현

그 안에서 중요한건, 검색하고자하는 리스트 데이터를 경우에 맞게 넘겨주어야하므로, 

이미 거친 데이터는 제거하고 보내주기위해 함수안에서 list.remove() 후 태워 보내주고, list.add()로 돌려놓았다.

 

Stream 클래스에 AnyMatch를 사용하고자 했지만,

결과가 올바로 반환되지 않아 주석처리 하고 flag를 두었다.

 

잘 구현한것 같았지만,

words [] 배열에 target 문자가 없는 경우, 0을 반환하기 위한 검사문이

지저분한 느낌이 든다.