Sangil's blog

어떤문제

일까? (출처:https://programmers.co.kr/learn/courses/30/lessons/43163)

해당 문제는 begin과 target 단어가 주어지고, 주어진 단어 배열을 이용하여 한개의 알파뱃씩을 변경하여 begin에서 target으로 변환 할 수 있는 최소 단계를 찾는 문제이다.

어떻게

begin으로 부터 시작되는 트리를 만들어, 탐색할수 있는 노드들( 1개의 단어로 변환 가능한 )을 깊이 우선 탐색을 하여, target에 도달 했을 때의 depth를 반환 하면 답을 구할 수 있지 않을까 생각했다.

target 단어인 hit를 시작으로 변환 가능한 노드들을 따라서 깊이 탐색을 한다. 이때, stack이란 배열을 이용하여 탐색을 한 노드들을 제외하고 시작단어 + 단어의 개수인 최대 depth까지 탐색 하도록 한다. 이때, 탐색 노드와 target단어가 같으면 해당 depth를 리턴한다. 그러면 최종적으로 모든 노드들을 탐색하게 되고, 이때 리턴되는 최소값이 최소 변환 횟수가 된다.

코드

(https://github.com/ChoiSangIl/algorithm/tree/master/BFS%2CDFS/programmers_C30_L43163_words)

import java.util.ArrayList;
import java.util.Arrays;

public class A20210907 {

	public static void main(String[] args) {
		String begin = "hit"; 
		String target  = "cog";
		String[] words = {"hot", "dot", "dog", "lot", "log", "cog"};
		
		ArrayList<String> stack = new ArrayList<String>();
		int result = dfs(begin, target, words, stack, 0);
		System.out.println(result);
	}
	
	public static int dfs (String begin, String target, String[] words, ArrayList<String> stack, int depth) {
		stack.add(begin);
		System.out.println(stack);
		
		if(begin.equals(target)) {
			stack.remove(begin);
			return depth;
		}
		
		int result = 0;
		
		for(int i=0; i<words.length; i++) {
			int wordCheck = 0;
			
			//변환 가능한지 체크
			for(int j=0; j<words[i].length(); j++) {
				if(begin.charAt(j) == words[i].charAt(j)) {
					wordCheck = wordCheck + 1;
				}
			}
			
			//단어 변환이 가능하면, 해당 노드를 깊이 탐색한다.
			if(wordCheck == words[i].length()-1 && !stack.contains(words[i])) {
				int particleResult = dfs(words[i], target, words, stack, depth+1);
				if(result == 0) {
					result = particleResult;
				}else {
					if(particleResult != 0) {
						result = Math.min(result, particleResult);
					}
				}
			}
		}
		stack.remove(begin);
		return result;
	}
}

어떤게

어려웠을까?

단어가 변환 가능한지 체크 하는 부분을 처음엔 replace 하는 방법으로 구현을 하였는데, aaa -> aab와 같은 경우를 생각 하지 못했다. 그래서 words의 크기 -1개의 단어가 똑같은 단어가 있으면 통과되게 변경 하였다. (해당 체크로직을 사소하다고 생각하고 쉽게 넘어갔다, 다양한 케이스를 생각 못함)

개선할점

해당 접근방법으로 문제를 풀때, DFS보다 BFS방식으로 탐색을 하면 더욱 좋은 퍼포먼스가 나올 수 있겠다라는 생각이 들었다. DFS방식으로 풀면 최소값을 찾아야 하기 때문에 전체 노드들을 순회해야 하지만, BFS방식으로 풀면 target값을 처음 찾는 순간이 최소값이기 때문이다. 물론 최악의 경우는 비슷하겠지만... 다음엔 BFS방식으로 풀어봐야겠다.