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

https://programmers.co.kr/learn/courses/30/lessons/43163

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

 

이런 문제는 결국 그래프 개념(DFS나 BFS)을 활용해서 풀 수 있다. 다만 유사한 문제처럼 DFS를 사용할 경우 최악일 때에는 시간초과가 날 수도 있기 때문에 최대한 BFS를 활용하려고 하고 있다.

(실제로 이 문제는 DFS를 쓰면 시간초과가 났던 것 같다. => https://yoloaeee.tistory.com/19?category=954228) 

[프로그래머스] 레벨2 게임 맵 최단거리

 

 

그리고 결국 자바 자료구조 라이브러리 상에서 BFS는 큐를 사용하는 것이다. 기본적인 BFS를 큐로 구현하는 외에 추가적으로 만들어준 것은 문자열 2개를 받아서 다른 문자의 갯수를 출력하는 compare 메소드이다.

다만 이 문제에서 조금 생각해봐야할 부분은 답은 맞긴 했지만, target이 words 배열 안에 있어도 도달하지 못하는 경우이다. target이 words 배열 안에 아예 없는 경우와는 다르다. (그리고 이 부분은 예외처리를 해주었다.)

처음에는 아예 생각을 하지 못하고 구현했고, 정답 역시 맞았지만 아마 이 부분에 대한 예외가 처리되지 않았다고 생각한다. 만약 이 경우가 히든케이스로 나왔다면, 아마 어떤 경우인지 해결하지 못했을 것 같다.

 

 

import java.util.LinkedList;
import java.util.Queue;

class Solution
{
    public int compare(String a, String b)
    {
        int result = 0;
        
        for(int i=0; i<a.length(); i++)
        {
            if(a.charAt(i)!=b.charAt(i))
            {
                result++;
            }
        }
        
        return result;
    }
    
    public int solution(String begin, String target, String[] words)
    {
        int answer = 0;
        boolean[] chk = new boolean[words.length];
        boolean contain = false;
        Queue<String[]> q = new LinkedList<String[]>();
        q.add(new String[]{begin, answer + ""});
        
        for(int i=0; i<words.length; i++)
        {
            if(target.equals(words[i]))
            {
                contain = true;
            }
        }
        
        if(!contain)
        {
            return 0;
        }
        
        while(true)
        {
            begin = q.peek()[0];
            answer = Integer.parseInt(q.poll()[1]);
            
            if(begin.equals(target))
            {
                break;
            }
            
            for(int i=0; i<words.length; i++)
            {
                if(!chk[i] && compare(begin, words[i])==1)
                {
                    chk[i] = true;
                    q.add(new String[]{words[i], (answer+1) + ""});
                }
            }
        }
        
        return answer;
    }
}