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

문제 링크

1. 문제 해결

제한 사항
1. 각 단어는 알파벳 소문자로만 이루어져 있습니다.
2. 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
3. words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
4. begin과 target은 같지 않습니다.
5. 변환할 수 없는 경우에는 0를 return 합니다.

제한 사항이 많지만 읽다보면 꽤나 푸는 사람 입장에게 좋은 영향으로 작용된다.
필자는 BFS를 이용해서 문제를 해결했다. DFS로도 가능하다 👍

1-1. 주의해야할 점

1. 현재 선택한 단어가 제한 사항에 올바르게 걸러지는 지 확인.
2. 중복 연산을 방지하기 위해 1차원 boolean 배열을 이용하여 이전에 바꾼 단어를 표시.

2. 소스 코드

import java.util.*;
class Solution {
    public int solution(String begin, String target, String[] words) {
        return bfs(begin,target,words);
    }
    
    private int bfs(String b ,String t, String [] words){
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(b,0,new boolean[words.length]));
        
        while(!q.isEmpty()){
            Node cur = q.poll();

            if(cur.w.equals(t)){
                return cur.c;
            }
            
            for(int i =0 ; i < words.length; i++){
                if(!words[i].equals(cur.w) && !cur.visited[i]){
                    //서로 다른 단어
                    if(checkSpelling(words[i],cur.w)){
                        boolean[] visited=  new boolean[words.length];
                        System.arraycopy(cur.visited,0,visited,0,cur.visited.length);
                        visited[i]=  true;
                        q.add(new Node(words[i],cur.c+1,visited));
                    }
                }
            }
        }
        
        return 0;
    }
    
    private boolean checkSpelling(String s1, String s2){
        if(s1.length() != s2.length()) //단어 길이가 서로 다른 경우
            return false; 
        
        int count = 0;
        for(int i= 0 ; i < s1.length(); i++){
            if(s1.charAt(i) != s2.charAt(i))
                count++;
        }
        
        if(count != 1) //스펠링이 한 개 이상 다른 경우
            return false;
        
        return true;
    }
    
    private class Node{
        boolean[] visited; 
        String w;
        int c;
        
        public Node(String w, int c, boolean []v){
            this.w = w;
            this.c =c;
            this.visited= v;
        }
    } 
}