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

문제

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

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

풀이

가장 짧은 변환 과정을 찾는 것이므로 BFS를 이용해서 탐색하였다.

Node를 만들어서 현재 word의 정보와 현재까지의 count를 저장해 주었고 이를 q에 넣어주었다.

 

현재 word가 다음에 변환할 수 있는 words를 찾아서 변환하였고, 현재 word가 target과 같아지면 현재 count를 반환하였다. 

 

변환할 수 있는지 확인하는 방법은 현재 word와 words[i]를 한 자리씩 비교하여 다른 자리수가 하나라면 true를, 아니라면 false를 반환하도록 구현하였다. 

 

코드

import java.util.*;
 
class Solution {
    public int solution(String begin, String target, String[] words) {
        boolean[] memo = new boolean[words.length];
        return bfs(begin, target, words, memo);
    }
    
    public int bfs(String begin, String target, String[] words, boolean[] memo) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(begin, 0));
        
        while(!q.isEmpty()) {
            Node node = q.poll();
            if(node.word.equals(target)) return node.count;
            for(int i = 0; i < words.length; i++) {
                //word가 words[i]로 변환될 수 있다면
                if(memo[i] == false && check(node.word, words[i])) {
                    memo[i] = true;
                    q.offer(new Node(words[i], node.count + 1));
                }
            }
        }
        return 0;
    }
    
    public boolean check(String s1, String s2) {
        int count = 0;
        for(int i = 0; i < s1.length(); i++) {
            if(s1.charAt(i) != s2.charAt(i)) count++;
        }
        if(count == 1) return true;
        return false;
    }
    
    public class Node {
        String word;
        int count;
        
        public Node(String word, int count) {
            this.word = word;
            this.count = count;
        }
    }
}