단어변환

Posted on Edited on In , ,

문제정의

시작단어에서 끝단어로 변환하는 최소 횟수를 알아내려고 한다. 만약 변환할 수 없다면 0을 반환한다. 변환을 거칠 땐 알파벳 한 글자만 바꿀 수 있다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import java.util.*;

public class TransformWord {
    
    //프로그래머스 level3 단어 변환
    public static int[][] matrix;
    public static void main(String[] args) {
        String begin = "hit";
        String target = "cog";
        String[] words = {"cog", "log", "lot", "dog", "dot", "hot"};

        List<String> list = new ArrayList<String>();

        list.add(begin);
        for(String s : words)
            list.add(s);

        matrix = new int[list.size()][list.size()];

        for(int i = 0; i < list.size(); i++)
        {
            for(int j = i+1; j < list.size(); j++)
            {
                if(canConnect(list.get(i), list.get(j)))
                {
                    matrix[i][j] = 1;
                    matrix[j][i] = 1;
                }
            }
        }
        
        final int inf = 1250;
        int[] distance  = new int[list.size()];
        boolean[] visited  = new boolean[list.size()];
        for(int i = 1; i < list.size(); i++)
            distance[i] = inf;

        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        while(!stack.empty())
        {
            int root = stack.pop();
            visited[root] = true;
            for(int i = 0; i < list.size(); i++)
            {
                if(matrix[root][i] == 1 && !visited[i])
                {
                    stack.push(i);
                    if(distance[i] > distance[root]+1)
                        distance[i] = distance[root]+1;
                }
            }
        }

        int index = list.indexOf(target);
        if(index == -1 || distance[index] == inf)
            System.out.println("false");
        else
            System.out.println(distance[index]);


    }
    public static boolean canConnect(String s1, String s2)
    {
        char[] arr1 = s1.toCharArray();
        char[] arr2 = s2.toCharArray();
        int wrong = 0;
        for(int i = 0; i < arr1.length; i++)
        {
            if(arr1[i] != arr2[i])
                ++wrong;
        }

        return wrong == 1 ? true : false;
    }
}
단어간의 변환 관계를 따지면 그래프를 만들 수 있다. 만든 그래프에서 begin에서 각 단어까지 변환하는데 걸리는 최소 변환 횟수를 구한다. 마지막으로 타겟 단어의 index에 해당하는 횟수를 반환하면 된다. 만약 타겟 단어가 없다면 0을 반환한다.

일단 그래프를 만들기 위해 두 단어가 변환이 되는 지 확인하는 함수 canConnect를 정의하였다. 모든 단어의 길이는 같다고 했으므로, 한쪽의 길이를 기준으로 하여 문자를 비교한다. 만약 다른 글자수(wrong)가 하나라면 true를 반환하고, 아니라면 false를 반환한다.

리스트 list를 만들어 첫시간과 words를 합친다. 반복문을 통해 모든 쌍을 canConnect를 통해 변환할 수 있는 관계인지 파악하고, 만약 변환할 수 있다면 matrix에 1이라 표시한다(18-30줄).

그래프를 matrix에 표시했으므로, dfs를 활용하여 최소 변환 횟수를 구할 차례이다. 이번 문제는 가능한 가 가능한지 않은가가 아니라, 최소를 찾아야 하므로 distance를 추가로 선언한다. 시작단어인 distance[0]은 0으로 하고 나머지는 큰 상수로 초기화한다.

이제 본격적인 dfs로 들어가보자. 스택에 0번을 넣고 vistied(방문했는지 여부)를 true로 한다. 그리고 변환할 수 있는 단어 중에 아직 방문하지 않은 단어들의 인덱스를 담는다. 이 때, 변환 횟수를 비교하는데 만약 현재 단어가 가지고 있는 distance값보다 현재 단어에서 1을 더한 값이 더 작다면 그 값으로 업데이트한다.

dfs를 모두 마치면 distance에는 시작단어에서 각각의 모든 단어로 변환할 수 있는 최소 횟수가 담기게 된다. 이제 indexOf()메소드를 이용하여 끝 단어의 인덱스를 구해 그 값을 반환하면 된다. 만약 끝단어의 distance값이 무한이거나 없을 경우에는 false를 출력하면 된다.

adjacency matrix를 사용하기 때문에, 최종 시간복잡도는 \(O(n^2)\)이다.

테스트



다른 사람의 풀이를 보니 그냥 dfs를 이용해서 풀었는데도 통과가 되었다. 그런데 그렇게 하면 최소값이 아니게 도달해도 정답이 되버릴텐데,, 이 부분에서 프로그래머스가 테스트 케이스를 추가해줬으면 좋겠다는 생각이 들었다.

이 문제를 풀면서 다익스트라를 참고도 안하고 혼자서 해보려고 했는데 나중에 다 풀고보니 다익스트라는 인접한 것 중에 가장 짧은 경로를 기준으로 가는 거라고 했다. 필자는 그냥 가장 나중에 확인한 것을 다음 노드로 지정하였는데 이렇게 해도 최단 거리를 찾을 수 있을지 궁금하다. 다음에 또 이런 문제를 만난다면 그 땐 다익스트라를 좀 더 세심하게 구현해야겠다. 덕분에 모자란 개념을 보충할 수 있었다.