프로그래머스 단어변환

문제 

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

최단 거리 탐색이므로 bfs를 이용한다 

현재 depth에 탐색된 경로를 포함해야하기 때문에 별도 모델에 넣어서 현재 queue의 뎁스를 표기한다 

제일 최초로 타겟에 유입하는 경로가 최단거리의 대상이다 

방문여부의 경우 이미 들어간 경우 그 경로가 다시 들어가면 이미 뎁스가 늘어나서 최단경로가 아니기 떄문에  초기화를 하지 않아도 된다 

 

String의 char로 각자 뽑아서 하나가 다른 경우에만 , 그리고 방문하지 않은 경우에만 대상을 넣어서 재탐색을 하면 된다 

 

문제 풀이 

public int solution(String begin , String target , String[] words){
	Queue<Temp> queue = new LinkedList<>();
    queue.offer(begin);
    
    int[] visited = new int[words.length];
    
    while(!queue.isEmpty()){
    	Temp poll = queue.poll();
        if(poll.getWord().equals(target)){
        	return poll.getIndex();
        }
        for(int i=0; i< words.length; i++){
        	int oneDeff =0;
            for(int j=0; j< words[i].length(); j++){
            	if(words[i].charAt(j) !=poll.getWord().charAt(j)){
					oneDeff++;
                }
            }
            if(visited[i] ==0 && oneDeff==1){
		    	poll.offer(new Temp(words[i],poll.getIndex()+1));
                visited[i] =1;
            }
            
        }
    }
	return 0;
}

class Temp{
	private String word;
    private int index;
    Temp(String word, int index){
    	this.word = word;
        this.index = index;
    }
    public String getWord(){
    	return word;
    }
    public int getIndex(){
    	return index;
    }
}