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

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

프로그래머스

 

Solution

import java.util.*;

class pack{
    String word;
    int cnt;
    
    public pack(String word, int cnt){
        this.word = word;
        this.cnt = cnt;
    }
}

class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        
        Queue<pack> q = new PriorityQueue<>((a,b)->a.cnt-b.cnt);
        boolean[] visit = new boolean[words.length];
        q.add(new pack(begin,0));

        while(!q.isEmpty()){
            pack curr = q.poll();

            if(curr.word.equals(target)) {
                answer = curr.cnt;
                break;
            }
            
            for(int i=0; i<words.length; i++){
                String word = words[i];
                if(check(curr.word, word) && !visit[i]){
                    q.add(new pack(word,curr.cnt+1));
                    visit[i] = true;
                }
            }
        }
        
        return answer;
    }
    
    public boolean check(String check, String target){
        int cnt =0; 
        for(int i=0; i<check.length(); i++){
            if(check.charAt(i)==target.charAt(i)) cnt++;
        }
        if(cnt == check.length()-1) return true;
        return false;
    }
}

 

최소 몇단계를 거치면 되는지를 구해야 하는 문제. BFS를 사용해서 풀어주었다. 

priorityQueue를 사용해 몇번째 이동중인지를 최소값이 먼저 큐에 담기도록 설정했다. 

visit 함수로 중복 방문이 되지 않도록 처리했는데, while문 안에서 이미 방문한 경우에 대한 조건을 빼먹는 실수를 했다.