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

프로그래머스 단어 변환

https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=java 

프로그래머스

아이디어

• 가장 짧은 변환 과정을 반환해야 하기 때문에 깊이 우선 탐색보다는 넓이 우선 탐색 BFS를 사용하는게 더 알맞다고 생각했다
• 큐에 단어와 몇번째 변환인지 저장하기 위해서 별도의 클래스를 정의했다
• 확인해야할 점은 한번에 하나의 단어만 변환할 수 있기 때문에 변환할 수 있는 단어인지 우선 확인해야한다
• 그렇기에 isConvert 함수를 통해서 다른 문자의 개수가 1개 이상이면 false를 반환하도록 했다
• BFS 함수 안에는 만약 시작 단어와 target 단어가 같으면 바로 return 하도록 했다
• 또한 isConvert 함수를 통해서 바꿀 수 없는 단어면 건너뛰고 마찬가지로 이미 방문했던 단어면 다시는 방문하지 않게 넘어가도록 했다
• 그렇게 걸러진 이후, words[i]는 방문처리가 되고 큐에 해당 단어와 현재 단계수 + 1 만큼 늘려서 저장해준다

코드

 

import java.util.*;

class Solution {
    static class Word {
        String word;
        int step;
        
        public Word(String word, int step) {
            this.word = word;
            this.step = step;
        }
    }
    
    public static boolean[] visited;
    public static int count = 0;
    
    public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];
        return(bfs(begin, target, words));     
    }
    
    public static boolean isConvert(String src, String dst) {
        char[] srcArr = src.toCharArray();
        char[] dstArr = dst.toCharArray();
        int diff = 0;
        for (int i=0; i<src.length(); i++) {
            if (srcArr[i] != dstArr[i]) {
                diff++;
            }
        }
        
        return diff == 1; // 1이 아니면 서로 다른 글자가 두개 이상이여서 바꿀 수 없음
    }
    
    public static int bfs(String begin, String target, String[] words) {
        Queue<Word> q = new LinkedList<>();
        q.offer(new Word(begin, 0));
        
        while (!q.isEmpty()) {
            Word w = q.poll();
            
            if (w.word.equals(target)) return w.step;
            
            for (int i=0; i<words.length; i++) {
                String str = words[i];
                if (!isConvert(w.word, words[i])) continue; // 단어가 2글자 이상 다르면 넘어감
                if (visited[i]) continue; // 방문했으면 진행
                visited[i] = true;
                q.offer(new Word(words[i], w.step+1));
            }
        }
        return 0;
    }
}