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

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

프로그래머스

 

사용 알고리즘

• BFS
• DFS

풀이

BFS를 사용한 풀이 

import java.util.*;
class Solution {
    
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        boolean [] visited = new boolean[words.length];
        Queue<String> q = new LinkedList<>();
        q.add(begin);
        
        while(!q.isEmpty()) {
            int size = q.size();
            for(int i = 0; i < size; i++){
                String cur = q.poll();
                
                if (cur.equals(target)) return answer;
                
                for(int j = 0; j < words.length; j++){
                    if (!visited[j] && check(words[j], cur)) {
                        visited[j] = true;
                        q.add(words[j]);
                    }
                }
            }
            answer++;
        }
        return 0;
    }
    
    private boolean check(String word, String cur) {
        int count = 0;
        for(int i = 0; i < word.length(); i++) {
            if (word.charAt(i) != cur.charAt(i)) {
                count++;
            }
        }
        
        if (count == 1) return true;
        else return false;
    }
}

회고

 

일단 BFS와 DFS를 사용한 풀이의 차이점부터 짚고 넘어가야 한다. 이 문제에서의 요구 사항은 가장 짧은 변환 과정을 찾는 것이고, BFS는 최단 경로 알고리즘을 찾는데 적합하다. 하지만, DFS는 모든 경로를 찾기 때문에 시간복잡도가 더 크다.

 

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

단어의 수가 50, 단어의 길이가 10이라고 가정할 때 BFS의 시간복잡도는 O(N^2 * M) => O(25000)이라 충분히 1초 안에 통과할 수 있다. 반면에 DFS는, O(2^N)이기 때문에 최악의 경우엔 2의 50승이라는 것인데 테케에 최악의 경우가 없어서 dfs로도 푸는 사람들이 있었다. 그래서 두 방법 모두 일단 알아보려고 한다.

BFS  풀이

1. 시작 단어를 큐에 담는다.
2. 큐가 빌 때 까지 반복하며, 현재 단어를 꺼내 cur라고 설정한다.
3. 종료 조건은 cur가 target이랑 일치할 때, 변환 횟수를 리턴한다.
4. 주어진 words 배열을 순회하며 현재 cur와 비교해서, 문자 하나만 다른 경우에 다시 큐에 넣어서 탐색을 진행해줘야 한다.
5. 추가적으로, 중복 탐색을 막기 위해서 방문 체크를 해줘야 한다.

 

단어가 큐에 추가되는 순서:

1. "hit" -> "hot"
2. "hot" -> "dot", "lot"
3. "dot" -> "dog", "lot" -> "log"
4. "dog" -> "cog", "log" -> "cog"

이렇게 된다. 

처음에

int size = q.size();
for(int i = 0; i < size; i++){
	...
}

왜 사이즈만큼 루프를 도는지 이해하지 못했는데, 현재 보고있는 문자와 한글자만 다른 모든 문자를 큐에 넣어야 해서 그렇다.

 

target까지 도달하는 경우의 수는 모두 = [5 4 6 5 6 5 5 4]인데, 최솟값인 4를 리턴해주면 된다.

 

맨 처음에 설정한 Integer.MAX_VALUE라는 값이 리턴할 때 변함이 없다면, target이랑 일치하는 문자가 없다는 뜻이므로 0을 반환해줘야 한다.

 

BFS, DFS 사고력 키우기 좋은 문제 추천!