[알고리즘] 프로그래머스 DFS/BFS 단어 변환 자바(JAVA) 풀이, 쉽게 알아보자

dfs/bfs 문제만 죽어라 풀 고 있다. 이번 문제는 쉽게 풀었던 것 같다. 이번 포스팅에서 풀이 과정에 대해서 간단히 알아보겠다.

 

문제

 

풀이 아이디어

• 문자열이 바뀌는 조건은 한개씩이기 때문에 다음과 같은 조건을 만족해야 한다.
  • 문자열의 길이는 차이가 나지 않는다 ( 원래 대상과 변경하려는 대상의 길이가 같다)
  • 문자열을 문자단위로 분해했을 때 한개의 차이만 있어야 한다.
• words에 있는 단어만이 변경하려는 대상이 될 수 있고 한번 대상이 된 words는 사용해서는 안된다.
• 위의 두 조건을 탐색하는 알고리즘으로 bsf를 선택하였다.

 

코드

public static Map<String,Boolean> visited = new HashMap<>();

public int solution(String begin, String target, String[] words) {
    int answer = 0;

    for (int i = 0; i < words.length; i++) {
        visited.put(words[i], false);
    }

    // targetn 과 같은지 검증
    answer = bfs(begin, target, words);

    System.out.println("answer = " + answer);
    return answer;
}

public static class StrNode{
    public String str;
    public int cnt;

    public StrNode(String str, int cnt) {
        this.str = str;
        this.cnt = cnt;
    }
}

public int bfs(String start,String target,String[] words) {
    Queue<StrNode> q = new LinkedList<>();

    q.offer(new StrNode(start,0));

    while (!q.isEmpty()) {
        StrNode tmp = q.poll();

        if(tmp.str.equals(target)){
            //answer = tmp.cnt;
            return tmp.cnt;
        }

        for (int i = 0; i < words.length; i++) {

            if(visited.get(words[i]) == true) continue;

            char[] tmpChars = tmp.str.toCharArray();
            char[] wordChars = words[i].toCharArray();

            if(tmpChars.length != wordChars.length) continue;

            int localCnt = 0;
            for (int j = 0; j < tmpChars.length; j++) {
                if(tmpChars[j] == wordChars[j]) localCnt++;
            }

            if (localCnt == tmpChars.length - 1) {
                //System.out.println("words[i] = " + words[i]);
                q.offer(new StrNode(words[i],tmp.cnt+1));
                visited.put(words[i], true);
            }
        }
    }

    return 0;

}