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

 

코드 구현

import java.util.*;
class Solution {
    public int solution(String begin, String target, String[] words) {
        Queue<WordState> queue = new ArrayDeque();
        boolean[] visited = new boolean[words.length];

        queue.offer(new WordState(begin,0));
        //방문 체크는 안해도 됨

        while (!queue.isEmpty()){
            //방문 (가까운 곳부터)
            WordState curr = queue.poll();
            //방문한 곳이 내가 찾던 target이라면 cnt를 return (중간에 빠지기. BFS이니 찾았으면 뒤는 없어!)
            if(curr.word.equals(target)) return curr.cnt;
            //next vertex 예약하기 전에, 1) next vertex를 먼저 찾아야 함
            //설명 : next vertex? 문자열 차이 계산해서 직접 연결 된 vertex 찾기
            //ex:) getDifferentCnt(curr.word,words[i]) => difference = 1이면 연결, 2면 연결X

            //2) 방문했는지 안했는지 체크, 방문 했을 때만 카운트+1
            for(int i=0;i<words.length;i++){
                if(getDifferentCnt(curr.word,words[i])==1){
                    if(!visited[i]){
                        queue.offer(new WordState(words[i],curr.cnt+1));
                        visited[i] = true;
                    }
                }
            }
        }

        return 0;
    }

    private int getDifferentCnt(String word, String word1) {
        int diffCnt = 0;
        for(int i=0;i<word.length();i++){
            if(word.charAt(i)!=word1.charAt(i)) diffCnt++;
        }
        return diffCnt;
    }

    class WordState{//자료구조 사용자 정의 class로 틀 만들기
        String word;
        int cnt;
        WordState(String word, int cnt){
            this.word = word;
            this.cnt = cnt;
        }

    }
}

재풀이

import java.util.*;
class Solution {
    public int solution(String begin, String target, String[] words) {
        int same=0;
        for(String s:words){
            if(s.equals(target)) same++;
        }
        if(same==0) return 0;
        Queue<String> queue = new ArrayDeque();
        boolean[] visited = new boolean[words.length];
        
        int cnt=0;
        queue.add(begin);
        while(!queue.isEmpty()){
            cnt++;
            int size=queue.size();
            for(int i=0;i<size;i++){
                String node = queue.poll();
                for(int j=0;j<words.length;j++){
                    if(!visited[j] && differentWord(node,words[j])==1){
                        if(words[j].equals(target)) return cnt;
                        queue.add(words[j]);
                        visited[j]=true;
                    }
                }
                
            }
        }
        return 0;
    }
    public int differentWord(String compare,String word){
        int cnt=0;
        for(int i=0;i<word.length();i++){
            if(compare.charAt(i)!=(word.charAt(i))){
                cnt++;
            };
        }
        return cnt;
    }
}

 

 

 

BFS를 활용해 어렵지 않게 풀 수 있었다.

자세한 내용은 주석을 참고하자!