[프로그래머스] 단어변환 - BFS(lv3)

programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환

import java.util.*;
class Solution {
    public int solution(String begin, String target, String[] words) {
        Queue<String> q = new LinkedList<String>();
        boolean check[] = new boolean[words.length];
        int answer = 1;
        outer: for(int i=0; i<words.length; i++) {
            boolean flag = false;
            for(int j=0; j<begin.length(); j++) {
                if(begin.charAt(j) != words[i].charAt(j)) {
                    if(flag == true) continue outer;
                    flag = true;
                }
            }
            if(flag==true) { // 1개가 바껴있다면 
                if(words[i].equals(target)) { // 정답이랑 같다면??
                    return answer;
                }
                check[i] = true;
                q.offer(words[i]);
            }
        }

        while(!q.isEmpty()) {
            int qSize = q.size();
            answer++;
            for(int qs=0; qs<qSize; qs++) {
                String cur = q.poll();
                outer: for(int i=0; i<words.length; i++) {
                    if(check[i] == true) continue;
                    boolean flag = false;
                    for(int j=0; j<cur.length(); j++) {
                        if(cur.charAt(j) != words[i].charAt(j)) {
                            if(flag == true) continue outer;
                            flag = true;
                        }
                    }
                    if(flag==true) { // 1개가 바껴있다면 
                        if(words[i].equals(target)) { // 정답이랑 같다면??
                            return answer;
                        }
                        check[i] = true;
                        q.offer(words[i]);
                    }
                }
            }
        }

        return 0;
    }
}

소요시간: 40분

begin	target	words[]
hit	cog	hot, dot, dog, lot, log, cog

hit -> cog로 가는데 

우선 begin과 words를 비교해서 문자 하나만 다른것들을 큐에 넣은 다음에

다음 로직에서는 큐사이즈만큼 반복하면서 큐에 값을 뽑고 갈 수 있는 단어가 있으면 큐에 넣고, target과 같으면 종료했다.

여기서 중복처리는 check[]을 이용해서 했는데 각 값에 대해서 1번이상 갈 일이 없으므로 하나만을 이용했다.