프로그래머스 level3 - 단어 변환(java)

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

문제 설명

두 개의 단어 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단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

아이디어

1. bfs 탐색
2. 변환 단계 저장
3. 한 개의 알파벳을 바꾸면 변환할 수 있는 단어인지?
4. 이전에 사용한 단어가 아닌지? (방문체크)

코드

package level3;

import java.util.*;

public class 단어변환 {
	public int solution(String begin, String target, String[] words) {
		return bfs(begin, target, words);
	}

	private int bfs(String begin, String target, String[] words) {
		Queue<String> q = new LinkedList<>();
		Set<String> v = new HashSet<>(); // 방문 체크
		v.add(begin);
		q.offer(begin);

		int result = 0; // 단계
		while (!q.isEmpty()) {
			int size = q.size();
			for (int t = 0; t < size; t++) {
				String cur = q.poll();
				
				// 타겟이면 리턴
				if (cur.equals(target)) {
					return result;
				}
				for (String word : words) {
					// 방문 여부와 알파벳 한개 바꿔서 변환 가능한지 여부
					if (!v.contains(word) && canNext(cur, word)) {
						v.add(word);
						q.offer(word);
					}
				}
			}
			result++;
		}
		return 0;
	}
	// 알파벳 한개 바꿔서 변환 가능한지 여부
	private boolean canNext(String cur, String word) {
		int differCount = 0;
		for(int i = 0; i < cur.length(); i++) {
			if(cur.charAt(i) != word.charAt(i)) {
				differCount++;
			}
			if(differCount > 1) {
				return false;
			}
		}
		return differCount == 0 ? false : true;
	}
}