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

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

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

import java.util.LinkedList;
import java.util.Queue;
class Solution {
	    public int solution(String begin, String target, String[] words) {        
	       
            return  bfs(begin, target, words);
	    }

		private int bfs(String begin, String target, String[] words) {
			boolean visited[] = new boolean[words.length];
			int cnt=-1;
			Queue<String> queue= new LinkedList<>();
			queue.offer(begin);
			
			while(true) {
				int size=queue.size();
				if(size==0) return 0;
				cnt++;
				for(int i=0; i<size; i++) {
					String str=queue.poll();
					if(str.equals(target)) return cnt; //target 과 같아진다면 끝 
					
					for(int j=0; j<words.length; j++) {
						if(visited[j]) continue;
						if(check(words[j],str)) {
							queue.offer(words[j]);
							visited[j]=true;
						}
					}
				}
			}
		}

		private boolean check(String word, String str) {
			int len=str.length();
			int cnt=0;
			
			for(int i=0; i<len; i++) {
				if(word.charAt(i)==str.charAt(i)) cnt++;
			}
			if(cnt==len-1) return true;
			return false;
		}
	}

소요시간 : 30분

 

BFS를 돌리면서 현재 단어에서 글자하나를 바꿧을 때 바꿀 수 있는 단어를 큐에 넣었습니다.

 

처음에 테스트케이스 3번이 나오지 않았는데 알고보니 글자하나를 바꿧을 때 가능한 글자인지 확인하는 함수에서 오류가 있었습니다.

 

예를 들어 hit -> hot 으로 변환은 가능합니다. 하지만 hit -> hto 로 변화는 불가능합니다.

인덱스를 확인하지 않고 그냥 글자만 있는지 확인해서 틀렸습니다.

 

이것만 실수 안한다면 쉬운문제라고 생각합니다!