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

문제 설명

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

입출력 예

begin	target	words	return
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

 

문제 풀이

이 문제의 핵심 키워드는 "모든 단어의 길이는 같다", "최소 변환 횟수"입니다.

첫 번째 키워드를 통해 단어를 비교하는 조건에서 길이에 대한 조건을 빼도 된다는 것을 확인할 수 있으며 두 번째 조건을 통해 dfs보단 bfs가 더 적절하다는 것을 확인할 수 있습니다.

 

첫 번째 코드는 WordProcess라는 클래스를 만들어 변환된 횟수와 단어를 저장하고 visited를 통해 방문했는지 체크해주는 코드입니다.두 번쨰 코드는 Custom Class를 만들지 않고 visited배열을 boolean이 아닌 int로 만들어 방문 횟수를 저장해주는 코드입니다.여기서 주의해야할 점은 begin은 words 배열에 들어있지 않기 때문에 words->wordList로 리스트변환 후 추가,  visited 사이즈 또한 words.length+1 해주셔야 합니다. begin을 제일 마지막에 넣는 이유는 조건 중 words 배열에 begin과 동일한 문자는 들어가지 않는다는 조건이 없기 때문에 맨 처음에 넣었을 떄 문제가 생길 수 있어 마지막에 넣어줬습니다.

 

풀이 코드

import java.util.*;
class Solution {
    public int solution(String begin, String target, String[] words) {
        Queue<WordProcess> queue = new LinkedList<>();
        boolean[] visited = new boolean[words.length];
        
        queue.offer(new WordProcess(begin, 0));
        
        while(!queue.isEmpty()){
            WordProcess wp = queue.poll();
            
            if(wp.getWord().equals(target)) return wp.getCnt();
            
            for(int i=0; i<words.length; i++){
                if(!visited[i] && getDiffCnt(wp.getWord(), words[i]) == 1){
                    visited[i] = true;
                    queue.offer(new WordProcess(words[i], wp.getCnt()+1));
                }
            }
        }
        return 0;
    }
    
    private int getDiffCnt(String word, String comp){
        int cnt = 0;
        for(int i=0; i<word.length(); i++){
            if(word.charAt(i) != comp.charAt(i)) cnt+=1;
        }
        return cnt;
    }
}

class WordProcess{
    String word;
    int cnt;
    
    public WordProcess(String word, int cnt){
        this.word = word;
        this.cnt = cnt;
    }
    
    public String getWord(){
        return word;
    }
    
    public int getCnt(){
        return cnt;
    }
}

 

import java.util.*;
class Solution {
    public int solution(String begin, String target, String[] words) {
        Queue<String> queue = new LinkedList<>();
        List<String> wordList = new ArrayList(Arrays.asList(words));
        
        if(!wordList.contains(target)) return 0;
        
        wordList.add(begin); queue.offer(begin);
        int[] visited = new int[words.length+1];
        while(!queue.isEmpty()){
            String word = queue.poll();
            
            if(visited[wordList.indexOf(target)] != 0) break;
            
            for(int i=0; i<words.length; i++){
                if(visited[i] == 0 && getDiffCnt(word, words[i]) == 1){
                    visited[i] = visited[wordList.indexOf(word)]+1;
                    queue.offer(words[i]);
                }
            }
        }
        return visited[wordList.indexOf(target)];
    }
    
    private int getDiffCnt(String word, String comp){
        int cnt = 0;
        for(int i=0; i<word.length(); i++){
            if(word.charAt(i) != comp.charAt(i)) cnt+=1;
        }
        return cnt;
    }
}

<출처>

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

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