프로그래머스_DFS/BFS_단어 변환

문제 설명 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.   예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다.   두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.   제한사항 각 단어는 알파벳 소문자로만 이루어져 있습니다. 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다. words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다. begin과 target은 같지 않습니다. 변환할 수 없는 경우에는 0를 return 합니다.   입출력 예입출력 예 설명   예제 #1 문제에 나온 예와 같습니다.   예제 #2 target인 cog는 words 안에 없기 때문에 변환할 수 없습니다.

 

 

---

 

 

깊이 우선(DFS)으로 풀어도 되고 넓이 우선(BFS)으로 풀어도 됩니다. 하지만 여러 경우의 수의 결과가 모두 필요한 게 아니라 특정 조건에 도달하는 최단 경로를 파악할 때는 BFS가 조금 더 편한 것 같습니다. 이번에는 큐(Queue)를 이용한 BFS 방식으로 작성했습니다.

 

전체 반복문은 큐의 사이즈가 0개가 되거나, 검색할 수 있는 최대 갯수인 배열의 길이를 초과했을 때까지 돌아갑니다. 그안에서 한 깊이에 해당하는 큐의 갯수가 다시 반복문을 돌고 또 그안에서 배열을 돌며 값을 비교하는 반복문이 포함됩니다.

 

C에서 미로찾기 만들 때가 생각나서 C스타일로 만들어봤더니 코드가 좀 지져분해졌습니다. 큐는 그냥 리스트를 썼지만요..ㅎㅎ

 

 

* 전체 코드

package pojoPrj;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {

	public int solution(String begin, String target, String[] words) {

		// target이 없을 경우 체크
		boolean check = false;
		for (String s : words) {
			if (s.equals(target)) {
				check = true;
				break;
			}
		}
		if (!check) {
			return 0;
		}

		List<String> queue = new ArrayList<>();
		queue.add(begin);

		int depth = 0; // bfs 깊이
		boolean status = false; // 최종값을 찾았는지 체크

		// bfs 시작
		while (queue.size() != 0 && depth <= words.length) {

			// 현재 queue에 들어 있는 큐를 한 세트(깊이)로 반복 수행
			int size = queue.size();
			for (int i = 0; i < size; i++) {

				for (int j = 0; j < words.length; j++) {

					// 문자열 다른 갯수
					int diff = compareWords(queue.get(0), words[j]);

					// 한글자만 다른 경우
					if (diff == 1) {

						// 찾았을 경우
						if (words[j].equals(target)) {
							depth++;
							status = true;
							break;

						// 아닐 경우
						} else {
							queue.add(words[j]);
						}
					}

				}

				if (status) {
					break;
				}

				queue.remove(0);

			}

			if (status) {
				break;
			}

			depth++;
		}

		return depth;
	}

	/**
	 * 두 문자열의 다른 글자 갯수 산출
	 * 
	 * @param s1 : 비교 문자열 1
	 * @param s2 : 비교 문자열 2
	 * @return
	 */
	private int compareWords(String s1, String s2) {

		int length = s1.length();

		// 다른 글자 갯수 카운트
		int diff = 0;
		for (int i = 0; i < length; i++) {
			if (s1.charAt(i) != s2.charAt(i)) {
				diff++;
			}
		}

		return diff;
	}
}