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

 

BFS

begin 단어를 target 단어로 만들기 위해 words에 있는 단어들로 변환해 가려고 한다. 근데 단어는 한글자만 바꿀 수 있을 때 최소 몇번 바꿔서 target단어를 만들 수 있는지 구하는 문제

 

접근 방법

큐에 begin부터 넣고, words에 있는 문자열 중, 아직 방문하지 않았고, 한글자만 차이나는 글자를 큐에 지금까지의 변환 횟수 +1과 함께 넣는다. 방문 체크

 

이때 방문여부를 체크하기 때문에 아직 지금의 문자열이 지나온 경로에서 방문하진 않았지만, 이미 방문 체크가 되어있는 단어는 방문하지 못한다는 것 때문에 헷갈렸는데 

 

예를 들어, hot -> dot, lot이 될 수 있고, 이때 이미 이 3개 단어는 방문으로 체크됨.

-> dot은 lot이랑도 한글자 차이지만 lot으로 바꾸는 경우는 체크하지 못하게 되는데, 이는 어차피 lot으로 가는 더 빠른 경로가 있을 것이라서 굳이 dot->lot의 경우를 체크하지 않는 것.

이라고 써보니 이해가 됐다.

 

 

소스코드

 

Java로 타입 선언해서 사용하기(생성자 무족건), Queue는 pop -> poll , push -> offer

String 비교 equals()로 해야함

String 인덱스 .charAt(index)로 접근

Int max값은 Integer.MAX_VALUE

import java.util.*;

class Pair {
    String str;
    int cnt;
    
    public Pair(String str, int cnt) {
        this.str = str;
        this.cnt = cnt;
    }
} 

class Solution {
    
    int answer = Integer.MAX_VALUE;
    
    public boolean isADifferent(String a, String b) {
        int cnt = 0;
        for(int c = 0 ; c < a.length(); c++) {
            if (a.charAt(c) != b.charAt(c)) {
                cnt++;
                if(cnt > 1) {
                    break;
                }
            }
        }
        if (cnt == 1) {
            return true;
        } else {
            return false;
        }
    }
    
    
    public int solution(String begin, String target, String[] words) {
        
        boolean visit[] = new boolean[50];

        Queue<Pair> queue = new LinkedList<>();
        Pair start = new Pair(begin, 0);
        queue.offer(start);
        
        while(!queue.isEmpty()) {
            Pair now = queue.poll();
            if(now.str.equals(target) && answer > now.cnt) {
                answer = now.cnt;
            }
            
            for(int i = 0 ; i < words.length ; i++) {
                // 방문한적 없고, 글자가 now랑 하나만 달라야함
                if(!visit[i] && isADifferent(now.str, words[i])){
                    visit[i] = true;
                    queue.offer(new Pair(words[i], now.cnt + 1));
                }
            }
        }
        
         return (answer == Integer.MAX_VALUE) ? 0 : answer;
    }
}