링크

문제링크

문제

두 개의 단어 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
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

해결

최단거리를 구하기위해 bfs로 구한 깊이에서 최솟값을 판별하였다.

countMatchingChar() 로 단어끼리 몇글자가 같은지 리턴해준다.
visitedNode를 사용하여 방문한 단어를 표시하고 방문하지 않고
한 글자만 다른 단어가 있다면 다음단어로 선정한다.

dep은 51로 초기화하여 선언한다. words의 길이는 50이하이기 때문에 depth는 50을 넘을수 없다.
현재 dep값과 bfs에서 반환된 dep값을 비교하여 최솟값을 구한다.

리턴된 값이 51이라면 단어를 끝까지 찾지 못한 경우이므로 0으로 바꾸어준다

코드

import java.util.Arrays;

class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        String curWord = begin;
        boolean[] visitedNode = new boolean[words.length];

        answer = bfs(curWord, target, words, visitedNode, 0);
        if(answer > 50) answer = 0;
        
        return answer;
    }
    
    private static int bfs(String curWord, String target, String[] words, boolean[] visitedNode, int depth) {
        if (curWord.equals(target)) {
            return depth;
        }

        int dep = 51;  //words는 50개 이하이기에 depth는 최대 50이다

        for (int i = 0; i < words.length; i++) {
            boolean[] copiedVisitedNode = Arrays.copyOf(visitedNode, visitedNode.length);

            if (copiedVisitedNode[i] == false && countMatchingChar(curWord, words[i]) == words[i].length() - 1) {
                copiedVisitedNode[i] = true;
                dep = Math.min(dep, bfs(words[i], target, words, copiedVisitedNode, depth + 1));
            }
        }

        return dep;
    }

    private static int countMatchingChar(String curWord, String nextWord) {
        int matchCharCount = 0;

        for (int i = 0; i < curWord.length(); i++) {
            if (curWord.charAt(i) == nextWord.charAt(i)) {
                matchCharCount++;
            }
        }

        return matchCharCount;
    }
}