[프로그래머스] DFS/BFS - 단어 변환

단어를 만들 수 있는 가장 적은 변환 횟수를 리턴하는 문제라

너비 우선 탐색을 이용하겠다고 생각하였다.

 

탐색 구현까지는 어쩨 저쩨 했는데

최소 횟수를 어떻게 구하나 막막하던 쯤

Node를 만들기로 하였고 Node 클래스를 만들어 문제를 해결하였다.

 

package algorithmStudy;

import java.util.*;

class Node{
	String val;
	int level;
	public Node(String v,int l) {
		val=v;
		level=l;
	}
}

public class dfsbfs {
	static boolean check(String a,String b) {
		int num=0;
		for(int i=0;i<a.length();i++) {
			if(a.charAt(i)!=b.charAt(i)) num++;
		}
		return num==1?true:false;
	}
	
	static int solution(String begin, String target, String[] words) {
        int answer = 0;
        
        Queue<Node> q = new LinkedList<>();
        boolean[] visited=new boolean[words.length];
        for(int i=0;i<words.length;i++) {
        	visited[i]=false;
        	if(begin.equals(words[i])) 
        		return 0;
        }
        
        q.add(new Node(begin,0));
        
        while(!q.isEmpty()) {
        	Node cur=q.poll();
        	if(target.equals(cur.val)) return cur.level;
        	for(int i=0;i<words.length;i++) {
        		//방문하지 않았고 1개의 문자만 다르다면
        		if(!visited[i] && check(cur.val,words[i])) {
        			visited[i]=true;
        			q.add(new Node(words[i],cur.level+1));
        		}
        	}
        }
        return answer;
    }
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String begin="hit";
		String target="cog";
		String[] words= {"hot", "dot", "dog", "lot", "log", "cog"};
		
		System.out.println(solution(begin,target,words));
	}

}