단어변환 [프로그래머스][String][DFS][Graph]

 

[광고 누르면 오늘의 행운 상승!!]

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

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

이해가 잘 가지 않아서 블로그를 참고했다.

1. 참고사항 

- words배열의 단어들을 서로 간선으로 이어주고 bfs를 통해 가장 빠르게 이동할 수 있는 거리를 알아내었다.
- 문자열을 서로 비교하면서 틀린게 두개 이상이면 false를 반환하는
   isNext를 이용해 다음 간선인지를 판단했다.

2. 구현

- 큐에 begin을 시작으로 bfs를 시작한다.
- 큐의 요소가 target과 같으면 answer에 cnt를 담고 return;
- words배열을 돌면서 단어들이 간선으로 이어질 수 있는지 판단한다(isNext)
- 반복

answer를 출력한다.

import java.util.*;
import java.io.*;

class Solution {
    static class Node{
        String word;
        int cnt;
        
        public Node(String word, int cnt){
            this.word = word;
            this.cnt = cnt;
        }
    }
    static int answer;
    static Queue<Node> q;
    static boolean[] visited;
    public int solution(String begin, String target, String[] words) {

        q = new LinkedList<>();
        visited = new boolean[words.length];
        
        q.add(new Node(begin, 0));
        
        bfs(begin, target, words);
        return answer;
    }
    static void bfs(String begin, String target, String[] words){
          while(!q.isEmpty()){
            Node node = q.poll();
            if(node.word.equals(target)){
                answer = node.cnt;
                break;
            }
            
            for(int i=0; i<words.length; i++){
                if(!visited[i] && isNext(node.word, words[i])){
                    visited[i] = true;
                    q.add(new Node(words[i], node.cnt + 1));
                }
            }
        }
    }
    static boolean isNext(String node, String next){
        for(int i=0, cnt = 0; i<node.length(); i++){
            if(node.charAt(i) != next.charAt(i))
                cnt++;
            if(cnt > 1) 
                return false;
        }
        return true;
    }
    
}