[프로그래머스] 단어변환(43163)_DFS

문제

URL : 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 함수를 작성해주세요.

 

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

	begin	target	words	return
예제1	hit	cog	[hot, dot, dog, lot, log, cog]	4
예제2	hit	cog	[hot, dot, dog, lot, log]	0

 

코딩풀이

import java.util.LinkedList;
import java.util.Queue;

public class Solution_43163 {

	static int minResult = 0;
	
	public static void main(String[] args) {
		String begin = "hit";
		String target = "cog";
//		String[] words = {"hot", "dot", "dog", "lot", "log", "cog"};
		String[] words = {"hot", "dot", "dog", "lot", "log"};
		System.out.println(solution(begin, target, words));
	}
	public static int solution(String begin, String target, String[] words) {
        int answer = 0;
        boolean checked[] = new boolean[words.length];
        if(checkInWords(target,words)) {
        	minResult = Integer.MAX_VALUE;
        	dfs(begin, target, words, checked,0);
        }
        answer = minResult;
        return answer;
    }
	public static void dfs(String begin, String target, String[] words, boolean[] checked,int cnt) {
		if(begin.equals(target)) {
			minResult = Math.min(minResult, cnt);
			return;
		}
		
		Queue<String> q = new LinkedList<String>();
		for(int i=0;i<words.length;i++) {
			if(!checked[i]) {
				if(checkArrWord(begin,words[i])) {
					checked[i]=true;
					q.add(words[i]);
				}
			}
		}
		
		while(!q.isEmpty()) {
			dfs(q.poll(),target,words,checked,cnt+1);			
		}
		
	}
	public static boolean checkArrWord(String begin, String word) {
		String[] beginArr = begin.split("");
		String[] wordArr = word.split("");
		
		int cnt = 0;
		for(int i=0;i<beginArr.length;i++) {
			if(!beginArr[i].equals(wordArr[i])) {
				cnt++;
			}
		}
		
		if(cnt==1) {
			return true;
		}
		return false;
	}
	public static boolean checkInWords(String target, String[] words) {
		for(int i=0;i<words.length;i++) {
			if(target.equals(words[i])) {
				return true;
			}
		}
		return false;
	}
}

 

풀이 원리

1. 최소 값을 구해야하므로 너비 우선 탐색(dfs) 를 활용해서 풀이를 한다.

2. 예제2 와 같이 target인 cog가 words 안에 없기 때문에 변환할 수 없는 경우를 필터링한다. (checkInWords() 함수)

3. begin과 target 이 같은 경우는 탐색한 cnt 의 최솟값을 구한다.

4. 같지 않는 경우에는 begin과 words 함수에 들어있는 문자열을 비교해서 queue에 담는다. (checkArrWord() 함수)

5. queue에 담은 내용을 다시 dfs함수를 통해 다시 3, 4 번을 반복한다.