[알고리즘] 단어 변환(JAVA)

BFS

프로그래머스 레벨2의 단어 변환 문제이다.

이 문제는 가장 짧은 변환 과정을 찾아야하고 bfs 는 최단거리를 보장해주는 알고리즘이므로 bfs 를 사용해야한다.

좀 더 공부해봐야 알겠지만 dfs 는 최단 거리가 보장이 안될 수도 있지 않을까?

bfs 문제를 많이 풀어보지는 않아서 정확히는 모르겠지만 전에 푼 문제처럼 Queue 를 이용한다.

 

풀이

1. 너비 우선 탐색 알고리즘을 이용하여 탐색한다.
2. 큐에서 idx, move 의 초기값(0, 0)을 꺼내서 visited 에 방문 여부 겸 이동 수를 기록
3. 탐색 조건에 의해 변환할 수 없는 경우의 수는 걸러지고 남은 경우들은 각자의 최선의 선택으로 탐색
4. 탐색 후  다음 좌표를 큐에 저장하고 다음 좌표의 방문 여부 겸 이동 수를  visited 에 기록
5. 각자의 최선의 선택으로 탐색한 경우만 남았으므로 최단 변환 과정은 bfs의 값을 인덱스로 하는 visited 의 값
6. 큐가 비어서 탐색을 진행할 수 없는 경우 bfs 메서드는 0을 반환
7. 탐색 종료 후 bfs 의 결과 값을 인덱스로 하는 visited 의 값을 반환(0 이면 변환 불가라는 뜻이므로 0)

최종 코드

import java.util.*;
class Solution {
    // 너비 우선 탐색
    public int bfs(String[] new_words, int[] visited, String target) {
        Queue<int[]> que = new LinkedList<>();
        // 초기값 (idx, move) = (0, 0)
        que.add(new int[2]);
        
        // que 에서 idx 와 move 를 꺼내서 사용하며
        // que 가 비었다는건 words 를 모두 방문했다는 뜻이므로 변환 불가라는 뜻
        while(!que.isEmpty()) {
            int[] now = que.poll();
            int idx = now[0];
            int move = now[1];
            
            // 탐색 조건
            // 1. 방문하지 않은 words
            // 2. 바뀐 글자가 1개
            for (int i = 1; i < new_words.length; i++) {
                int diff = 0;
                // 바뀐 글자가 1개 뿐인지 체크
                for (int j = 0; j < new_words[i].length(); j++) {
                    if (new_words[idx].charAt(j) != new_words[i].charAt(j)){
                        diff += 1;
                    }
                }
                if (visited[i] == 0 && diff == 1) {
                	// 조건에 맞을 경우 이동수 +1
                    // visitied[i] 에 이동수 기록
                    move += 1;
                    visited[i] = visited[idx] +1;
                    // target 으로 변환 시 해당 visited의 인덱스 i 반환
                    if (new_words[i].equals(target)) {
                        return i;
                    }
                    que.add(new int[]{i, move});
                }
            }
        }
        return 0;
    }
    public int solution(String begin, String target, String[] words) {
        String[] new_words = new String[words.length +1];
        new_words[0] = begin;
        for (int i = 0; i < words.length; i++) {
            new_words[i +1] = words[i];
        }
        int[] visited = new int[new_words.length];
        int result = bfs(new_words, visited, target);
        
        // result = 도착점의 visited 인덱스
        // result 가 0 이면 변환 불가라는 의미
        // result 가 0 이 아니면 visited[result] 가 이동수
        return result == 0 ? 0 : visited[result] ;
    }
}