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

문제

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

풀이

BFS를 이용해 풀었다.
words 배열에 속해있는 단어들을 대상으로
특정 단어 두 개가 있을 때 서로 다른 알파벳이 단 하나 있을 때 true로 하는 2차원배열을 생성하였다.

예를 들어서, hit과 hot이 있으면

//두 단어에서 서로 다른 알파벳의 수가 1개일 경우
isPossible[hit][hot] = true;
//서로 다른 알파벳의 수가 2개 이상일 경우 
isPossible[hit][dog] = false;

실제로는 각 단어들로 인덱싱을 할 수 없기 때문에 HashMap을 이용해 각 단어들마다 특정 Integer로 치환하였다.

그 뒤 BFS를 이용해 최소 변환 횟수를 얻었다.

코드

import java.util.*;
class Solution {
    public class Word{
        int wordNum;
        int sum;
        public Word(int wordNum, int sum){
            this.wordNum = wordNum;
            this.sum = sum;
        }
    }
    public int solution(String begin, String target, String[] words) {
        int N = words.length;
        HashMap<Integer, String> map = new HashMap();
        for(int i=0;i<N;i++){
            map.put(i, words[i]);
        }
        boolean[][] isPossible = new boolean[N][N];
        
        for(int i=0;i<N;i++){
            for(int j=i+1;j<N;j++){
                if(isPossible(map.get(i), map.get(j))){
                    isPossible[i][j] = isPossible[j][i] = true;
                }
            }
        }
        Queue<Word> Q = new LinkedList();
        for(int i=0;i<N;i++){
            if(isPossible(begin, map.get(i))) Q.add(new Word(i, 1));
        }
        boolean[] visited = new boolean[N];
        while(!Q.isEmpty()){
            Word curWord = Q.poll();
            int cur = curWord.wordNum;
            int sum = curWord.sum;

            if(visited[cur]) continue;
            visited[cur] = true;

            if(map.get(cur).equals(target)) return sum;
            
            for(int i=0;i<N;i++){
                if(isPossible[cur][i] && !visited[i]){
                    Q.add(new Word(i, sum+1));
                }
            }
        }
        
        return 0;
    }
    
    public boolean isPossible(String str1, String str2){
        boolean ret = false;
        for(int i=0;i<str1.length();i++){
            if(str1.charAt(i) != str2.charAt(i)){
                if(!ret) ret = true;
                else return false;
            }
        }
        return true;
    }
    
}