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

📌문제

📄 프로그래머스 - 단어변환문제

프로그래머스 DFS/BFS 카테고리에 있는 "단어변환"문제다.
DFS를 이용하여 풀었다.

📌로직

문제에 있는 테스트케이스로 그림을 한번 그려봤다.

주어진 words 리스트에 target문자열이 있는지 먼저 체크 한 후
target문자열이 있다면 아래 그림처럼 모든 경우의 수를 탐색한다.

begin 부터 시작해 변환 가능한 단어로 가지치기 하듯이 모든 경우를 모두 찾아 카운트를 한다.
가지치기(?) 한곳에서 카운트가 작은 쪽이 리턴된다.
이 과정을 반복하여 최종적으로 모든 경우의 수 중 가장 작은 값이 리턴된다.

정리하면

1. words 에 target 있는지 확인
2. 단어변환 경로 탐색
2-1. target이 되었을때 RETURN (탈출조건)
2-2. 가능한 단어 체크 후 재귀(2번으로)

📌테스트케이스

- "begin", "target", words //결과

- "hit", "cog", {"hot", "dot", "dog", "lot", "log", "cog"}	//4
- "hit", "log", {"hot", "dot", "dog", "lot", "log", "cog"}	//3
- "hit", "cog", {"cog", "log", "lot", "dog", "dot", "hot"}	//4
- "hit", "cog", {"hot", "dot", "dog", "lot", "log"}		//0
- "1234567000", "1234567899", {"1234567800", "1234567890", "1234567899"}//3

📌코드

public int solution(String begin, String target, String[] words) {
	int n = words.length;
    
	/* 1. words 에 target 있는지 확인*/
	int index = -1;
	for(int i = 0 ; i < n ; i++) {
		if(words[i].equals(target)) index = i;
	}
	if(index< 0) {
		return 0;
	}
	/* 2. 단어변환 경로 탐색 */
	boolean[] chk = new boolean[n];
	return dfs(begin, target, -1, words, chk, 0);
}

/**
 * 단어변환의 모든 경로 탐색 최저 카운트 수 반환
 */
public int dfs(String begin, String target, int idx, String[] words, boolean[] chk , int cnt) {		
	/* target이 되었을때 RETURN (탈출조건) */
	if(target.equals(begin)) {
		return cnt;
	}
	
	/* 방문체크, 카운트 */
	if(idx >= 0) chk[idx] = true;
	cnt++;
	
	/* 가능한 단어 체크 후 재귀 */
	int answer = chk.length;
	for(int i=0 ; i<chk.length ; i++) {			
		if(!chk[i]) {
			if(wordCheck(begin.toCharArray(), words[i].toCharArray())) {
				answer = Math.min(answer, dfs(words[i], target, i, words, chk, cnt));
				chk[i] = false;
			}
		}
	}
	return answer;
}

/**
 * 가능한 단어인지 체크 
 */
public boolean wordCheck(char[] begin, char[] target) {
	/* 한글자만 다른지 체크 */
	int cnt = 0;
	for(int j=0 ; j<begin.length ; j++) {
		if(begin[j] != target[j])
			cnt ++;
	}
	return (cnt ==1) ? true : false;
}

📌마무리

재귀 로직을 생각하느라 좀 헤맸다. 아직 재귀 문제를 풀면 뫼비우스 띠에 빠지는 느낌이다..

dfs 메서드에 파라미터가 너무 주렁주렁 달려있어서 줄이고 싶은데 일단 저게 최선이다😥

아직 BFS 알고리즘은 뭔지, DFS/BFS 중 뭘 이용해야 효율적인지 모르겠다. 다음엔 BFS 공부해서 DFS/BFS 알고리즘을 한번 정리 해봐야겠다!