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

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

프로그래머스

 

⭐️ 중요 포인트

1. 현재 상태(Status)에서 내가 도달할 수 있는 word(단어끼리의 차이가 1 인 단어)를 찾아서 큐에 넣고 다시 방문하지 않도록 isVisited를 true로 설정한다. (isVisited를 설정하지 않으면 계속 같은 단어를 반복해서 돌거나 "최소"가 되지 않을 수 있다.)

2. cnt를 1 증가시키며 target에 도달할 때까지 반복. 이 때, 모두 반복했는데도 (isVisited가 모두 true가 된 경우 또는 Queue가 모두 비워진 경우) target에 도달하여 탈출하지 못하면 0을 반환한다.

 

 

(ex.

Phase 1. hit -> hot

Phase 2. hot -> dot | lot

Phase 3. dot -> dog, lot -> log

Phase 4. dog -> cog, log -> cog

)

 

import java.util.*;

class Solution {
    
    static class Status {
        String word;
        int cnt;
        
        Status(String word, int cnt) {
            this.word = word;
            this.cnt = cnt;
        }
    }
    
    static boolean[] isVisited;
    static String sBegin;
    static String sTarget;
    static String[] sWords;
    static int answer;
    
    static void init(String begin, String target, String[] words) {
        sBegin = begin;
        sTarget = target;
        sWords = words;
        
        isVisited = new boolean[words.length];
        answer = 0;
    }
    
    static boolean canChange(String s1, String s2) {
        int cnt = 0;
        
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                cnt++;
            }
        }
        
        return cnt == 1 ? true : false;
    }
        
    
    static int bfs() {
        Deque<Status> q = new ArrayDeque<>();
        q.add(new Status(sBegin, 0));
        
        while (!q.isEmpty()) {
            Status cur = q.pop();
            
            if (cur.word.equals(sTarget)) {
                return cur.cnt;
            }
            
            for (int i = 0; i < sWords.length; i++) {
                if (!isVisited[i] && canChange(cur.word, sWords[i])) {
                    q.add(new Status(sWords[i], cur.cnt + 1));
                    isVisited[i] = true;
                }
            }
        }
        return 0;
        
    }

    
    public int solution(String begin, String target, String[] words) {
        init(begin, target, words);
        
        return bfs();
    }
}