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

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

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

문제 설명

두 개의 단어 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 합니다.

풀이

1. 각 단어 간에 1글자 차이가 나면 변환이 가능하므로, 인접하다고 판단한다.

2. BFS로 인접한 단어를 순회하면서 각 단어의 방문순서를 저장한다.

3. Target 단어의 방문순서 중 가장 최솟값을 반환한다.

 

import java.util.*;

class Solution {
    
    public static ArrayList<Integer> A[];
    public int visited[];
    public int minConvert = 0x7FFFFFFF;
    
    public boolean isAdjacent(String a, String b){
        int diff = 0;
        boolean ret = true;
        
        for(int i=0; i<a.length(); i++){
            if(a.charAt(i) != b.charAt(i)) diff++;
            if(diff >= 2){
                ret = false;
                break;
            }
        }
        
        return ret;
    }
    
    public void initialize(){
        for(int i=0; i<visited.length; i++){
            visited[i] = -1;
        }
        return;
    }
    
    public void BFS(int beginIdx, int targetIdx){
        
        Queue<Integer> q = new LinkedList<>();
        
        q.offer(beginIdx);
        visited[beginIdx] = 1;
        
        while(!q.isEmpty()){
            int front = q.poll();
            for(int i=0; i<A[front].size(); i++){
                int next = A[front].get(i);
                if(visited[next] == -1){
                    q.offer(next);
                    visited[next] = visited[front] + 1;
                }
            }
        }
        
        minConvert = Math.min(minConvert, visited[targetIdx]);
        
        return;
    }
    
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        boolean exists = false;
        
        // target이 words 에 존재하지 않을 경우
        for(int i=0; i<words.length; i++){
            if(words[i].equals(target)){
                exists = true;
                break;
            }
        }
        
        if(!exists) return 0;
        
        // words[i] 와 인접한 단어들의 idx를 저장할 인접 리스트
        A = (ArrayList<Integer>[])new ArrayList[words.length];
        visited = new int[words.length];
        
        for(int i=0; i<words.length; i++){
            A[i] = new ArrayList<Integer>();
            visited[i] = -1;
        }
        
        for(int i=0; i<words.length; i++){
            for(int j=0; j<words.length; j++){
                if(i==j) continue;
                if(isAdjacent(words[i], words[j])){
                    A[i].add(j);
                }
            }
        }
        
        int beginIdx = words.length, targetIdx = -1;
        
        for(int i=0; i<words.length; i++){
            if(words[i].equals(target)){
                targetIdx = i;
            }
        }
        
        for(int i=0; i<words.length; i++){
            if(isAdjacent(begin, words[i])){
                initialize();
                BFS(i, targetIdx);
            }
        }
        
        answer= minConvert;
        
        return answer;
    }
}