[Algo Rhythm🕺💃] 프로그래머스 고득점 kit 단어변환

📚 문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

 

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

 

예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.

• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.

• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.

• begin과 target은 같지 않습니다.

• 변환할 수 없는 경우에는 0를 return 합니다.

 

🎯 어떻게 풀었나

import java.util.Arrays;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(String begin, String target, String[] words) {
        if(!Arrays.stream(words).anyMatch(e -> e.equals(target))) return 0;
        
        int answer = 0;
        int root = 0,tIdx = 0;
        ArrayList<String> wordList = new ArrayList<>(Arrays.asList(words));
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        Queue<Integer> q = new LinkedList<>();
        
        if(!Arrays.stream(words).anyMatch(e -> e.equals(begin))) wordList.add(begin);
        
        boolean[] visited = new boolean[wordList.size()];
        
        // init graph
        for(int i = 0; i < wordList.size(); i++) {
            if(wordList.get(i).equals(begin)) root = i;
            if(wordList.get(i).equals(target)) tIdx = i;
            
            ArrayList<Integer> lst = new ArrayList<>();
            for(int j = 0; j < wordList.size(); j++) {
                if(i == j) continue;
                if(isOneDiff(wordList.get(i), wordList.get(j))) lst.add(j);
            }
           graph.add(lst);
        }
        
        // BFS
        q.add(root);
        q.add(null);
        while(!q.isEmpty()) {
            if(q.element() == null) {
                answer++;
                q.remove();
            }
            
            int parent = q.remove();
            visited[parent] = true;

            boolean found = false;
            
            for(int child : graph.get(parent)) {
                if(visited[child] == false) {
                    q.add(child);
                }
                if(child == tIdx) {
                    found = true;
                    break;
                }
            }
            
            if(found) break;
            
            q.add(null);
        }
        
        return answer + 1;
    }
    
    public boolean isOneDiff(String s1, String s2) {
        int nDiff = 0;
        for(int i = 0; i < s1.length(); i++) {
            if(s1.charAt(i) != s2.charAt(i)) nDiff++;
            if(nDiff > 1) return false;
        }
        return true;
    }
}

 

🧐 왜 저렇게 풀었나

알고리즘은 간단하다.

먼저 매개변수로 주어지는 'begin'과 배열 'words'를 합쳐서 노드들의 집합을 만든다.

그리고나서 이 노드들을 이용해서 그래프를 만들어주는데 그래프는 ArrayList를 사용한 인접 리스트로 표현했다. 정확히 한 글자만 다를 경우 변환할 수 있기 때문에 한 글자와 다른 글자가 정확히 한 글자만 다를 경우 이어지도록 했다.

그래프를 만든 후부터는 간단하다. BFS를 통해 target을 가장 먼저 찾았을 떄의 level을 구하면 된다. 이 때 한 가지 주목해야 할 스킬이 큐에 null을 넣어서 BFS를 하면서 level을 구분했다는 것이다.

 

📖 무엇을 배웠나

BFS를 할 때 null을 넣어서 level을 구분하는 스킬을 배웠다!