[Programmers] 단어 변환 (Java)

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

프로그래머스

---

간단한 BFS 문제이다.

알고리즘

1. begin 문자열과 0을 같이 큐에 넣는다.
2. 큐가 빌 때까지 아래의 실행을 한다.
   1. 큐에서 현재 문자열과 단계를 꺼낸다.
   2. 모든 진행 가능한 word 문자열에 대해 다음을 실행한다.
      1. 만약 해당 문자열에 이미 방문했다면 지나친다.
      2. 현재 문자열과 word 문자열의 다른 부분이 1개라면 방문 처리 하고 word를 단계 + 1 해서 큐에 삽입한다.
         만약 삽입할 문자열이 target과 같다면 바로 답을 저장한다.

정답 코드

import java.util.*;

class Solution {
    
    boolean[] vis = new boolean[51];
    
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        Queue<Progress> q = new LinkedList<>();
        q.offer(new Progress(begin, 0));
        while (!q.isEmpty()) {
            Progress progress = q.poll();
            for (int i = 0; i < words.length; i++) {
                if (vis[i]) continue;
                String word = words[i];
                if (countDiff(progress.cur, word) == 1) {
                    if (word.equals(target)) {
                        answer = progress.step + 1;
                        break;
                    }
                    q.offer(new Progress(word, progress.step + 1));
                    vis[i] = true;
                }
            }
            if (answer != 0) break;
        }
        return answer;
    }
    
    class Progress {
        String cur;
        int step;
        Progress (String cur, int step) {
            this.cur = cur;
            this.step = step;
        }
    }
    
    int countDiff (String cur, String word) {
        int cnt = 0;
        for (int i = 0; i < cur.length(); i++) {
            if (cur.charAt(i) != word.charAt(i)) {
                cnt++;
            }
        }
        return cnt;
    }
}