단어 변환(프로그래머스, Java)

문제링크: https://programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환 | 프로그래머스

알고리즘 설명:

한글자씩 바꿔가면서 맞는 단어가 있다면 그 값을 가지고 다시 함수를 호출하고 target의 값과 같아질 때 까지 몇번 함수를 호출한지를 구하는 문제이다.

• 문제 조건에 있듯이 target이 words에 존재하는 지 부터 확인 한 후 존재하는 경우 메서드를 호출한다.
• 전역변수로 visited를 관리하고 한 단어씩 받아와 한 글자씩 바꿔가면서 단어와 한 글자 바꾼 begin의 값이 같아지는 경우가 있는지 확인하고 같아지는 경우 그 단어를 begin이 들어 있던 인자 자리에 넣어 다시 자신을 호출을 한다.
• 호출된 모든 dfs 메서드에서는 answer 값을 1로 가지고 있고 계속 자신을 호출하다가 target과 바꾼 값이 같아지는 경우 return 1을 하여 answer 값에 + 해준다.( 메서드 호출 횟수)
• 물론 한 번 사용된 단어들은 visited에서 true로 바꿔 다시 접근 안하도록 걸러낸다.

막혔던 지점:

호출할 때 마다 카운트하는 코드를 깔끔하게 하지 못하였다.

answer = 1; 
answer += dfs(temp, target, words); 

// 이 부분은 계속 유용하게 사용할 것 같다.

 

package test;

public class WordConversion {
	static boolean[] visited;

	@SuppressWarnings("unchecked")
	public static int solution(String begin, String target, String[] words) {
		visited = new boolean[words.length];

		for (int i = 0; i < words.length; i++) {
			if (target.equals(words.clone()[i]))
				return dfs(begin, target, words);
		}
		return 0;
	}

	public static int dfs(String begin, String target, String[] words) {
		int answer = 0;
		String temp = "";
		for (int i = 0; i < words.length; i++) {

			if (visited[i])
				continue;

			for (int j = 0; j < words[i].length(); j++) {
				temp = begin;
				temp = (j > 0 ? begin.substring(0, j) : "") + words[i].charAt(j)
						+ (j < begin.length() - 1 ? begin.substring(j + 1) : "");
				if (temp.equals(target))
					return 1;
				if (temp.equals(words[i])) {
					visited[i] = true;
					answer = 1;
					answer += dfs(temp, target, words);
				}
			}
		}

		return answer;
	}

	public static void main(String[] args) {
		String begin = "hit";
		String target = "cog";
		String words[] = { "hot", "dot", "dog", "lot", "log", "cog" };

		System.out.println("답: " + solution(begin, target, words));

	}

}