LeetCode - Knight Dialer

문제 설명

The chess knight has a unique movement, it may move two squares vertically and one square horizontally, or two squares horizontally and one square vertically (with both forming the shape of an L). The possible movements of chess knight are shown in this diagaram:

A chess knight can move as indicated in the chess diagram below:

Given an integer n, return how many distinct phone numbers of length n we can dial.

You are allowed to place the knight on any numeric cell initially and then you should perform n - 1 jumps to dial a number of length n. All jumps should be valid knight jumps.

As the answer may be very large, return the answer modulo 109 + 7.

입출력 예시

Example 1:

Input: n = 1
Output: 10
Explanation: We need to dial a number of length 1, so placing the knight over any numeric cell of the 10 cells is sufficient.

Example 2:

Input: n = 2
Output: 20
Explanation: All the valid number we can dial are [04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]

Example 3:

Input: n = 3131
Output: 136006598
Explanation: Please take care of the mod.

제약사항

1 <= n <= 5000

Solution

1. Queue를 이용한 가능한 후보 탐색

[전략] 1. 각 다이얼에서 다음 유망한 후보지를 HashMap에 ArrayList로 저장해놓는다.
2. 동시에, 다음 후보 dial을 queue에 insert
3. n번의 사이클동안 큐에서 하나를 빼면서 다음 dial를 queue에 insert하는 것을 반복한다.

=> 시간초과

import java.util.*;

class Solution {

   public int knightDialer(int n) {

        if (n == 1) {
            return 10;
        }
        int[][] dials = { { 1, 2, 3 }, { 4, 5, 6, }, { 7, 8, 9 }, { -1, 0, -1 }};    

        HashMap<Integer, ArrayList<Integer>> dialstoNextDial = new HashMap<>();
        Queue<Integer> nextDialqueue = new LinkedList<>();
        
        for (int i = 0; i < dials.length; i++) {
            for (int j = 0; j < dials[i].length; j++) {
                if (dials[i][j] < 0) {
                    continue;
                }

                ArrayList<Integer> nextDials = new ArrayList<Integer>();
                //8가지 경우 체크해보기
  
                // -2 up + 1 right
                checkNextDialPossible(dials, i - 2, j + 1, nextDials);
                // -1 up + 2 right
                checkNextDialPossible(dials, i - 1, j + 2, nextDials);

                // 2 up + 1 right
                checkNextDialPossible(dials, i + 2, j + 1, nextDials);
                // 1 up + 2 right
                checkNextDialPossible(dials, i + 1, j + 2, nextDials);

                // -2 up - 1 right
                checkNextDialPossible(dials, i - 2, j - 1, nextDials);
                // -1 up - 2 right
                checkNextDialPossible(dials, i - 1, j - 2, nextDials);
                // 2 up - 1 right
                checkNextDialPossible(dials, i + 2, j - 1, nextDials);
                // 1 up - 2 right
                checkNextDialPossible(dials, i + 1, j - 2, nextDials);

                nextDialqueue.addAll(nextDials);

                dialstoNextDial.put(dials[i][j], nextDials);

            }
        }

       
        for (int k = 3; k <= n; k++) {
            int queueSize=nextDialqueue.size();
            for (int i = 0; i < queueSize; i++) {
                nextDialqueue.addAll(dialstoNextDial.get(nextDialqueue.remove()));
            }
        }
        int divideVal=1000000007;
        return nextDialqueue.size() % divideVal;
    }
    
    public void checkNextDialPossible(int[][] dials, int horizonIdx, int verticalIdx,
            ArrayList<Integer> nextPossibleDials) {
        if (horizonIdx >= 0 && horizonIdx<dials.length && verticalIdx>=0 && verticalIdx < dials[0].length) {
            int nextDial = dials[horizonIdx][verticalIdx];
            if (nextDial >= 0) {
                nextPossibleDials.add(nextDial);
            }
        }
    }
}

2. DFS

• 각 다이얼별로 길이 n까지의 경우의 수를 구해본다
  ==> 시간초과

 public int knightDialer2(int n) {

        if (n == 1) {
            return 10;
        }
        int[][] dials = { { 1, 2, 3 }, { 4, 5, 6, }, { 7, 8, 9 }, { -1, 0, -1 } };

        // HashMap<Integer, ArrayList<Integer>> dialstoNextDial = new HashMap<>();
        // Queue<Integer> nextDialqueue = new LinkedList<>();

        int count = 0;
        int divideVal = 1000000007;
        for (int i = 0; i < dials.length; i++) {
            for (int j = 0; j < dials[i].length; j++) {
                if (dials[i][j] < 0) {
                    continue;
                }
                count += dfsNextDial(dials, i, j, n, 1) % divideVal;
            }
        }

        return count;
    }

    public int dfsNextDial(int[][] dials, int horizonIdx, int verticalIdx, int n, int curTime) {

        if (horizonIdx >= 0 && horizonIdx < dials.length && verticalIdx >= 0 && verticalIdx < dials[0].length
                && dials[horizonIdx][verticalIdx] >= 0) {
            if (curTime == n) {
                return 1;
            } else {
                return dfsNextDial(dials, horizonIdx - 2, verticalIdx + 1, n, curTime + 1)
                        + dfsNextDial(dials, horizonIdx - 1, verticalIdx + 2, n, curTime + 1)
                        + dfsNextDial(dials, horizonIdx + 2, verticalIdx + 1, n, curTime + 1)
                        + dfsNextDial(dials, horizonIdx + 1, verticalIdx + 2, n, curTime + 1)
                        + dfsNextDial(dials, horizonIdx - 2, verticalIdx - 1, n, curTime + 1)
                        + dfsNextDial(dials, horizonIdx - 1, verticalIdx - 2, n, curTime + 1)
                        + dfsNextDial(dials, horizonIdx + 2, verticalIdx - 1, n, curTime + 1)
                        + dfsNextDial(dials, horizonIdx + 1, verticalIdx - 2, n, curTime + 1);
            }
        }
        return 0;
    }

3. DP

1번과 2번 풀이에서 시간을 줄일수 있는 방법을 생각해보았다.

discussion에 다른 사람들이 푼 문제를 참고하니 nextDial을 구하는 과정을 생략하고 처음에 2차원 배열로 선언하여 푸는게 보였다. 8가지 방향으로 체크를 해보고 hashmap에 담는 과정은 확실히 시간비용이 소요되는 일이지만, dial 갯수가 작은 점으로, 전체 시간초과에 영향을 미칠 요소는 아니라고 생각하였고
다이얼의 위치와 갯수가 바뀔 경우 머릿속으로 다시 생각해서 배열을 선언하는 것 보다 자동화하여 도출할수 있도록 하는게 낫다고 판단하였다.

그 다음으로 시간비용을 줄일 수 있는 부분을 생각한 것은 n번의 사이클동안 반복되는 구간이었다. queue와 dfs에서는 각각의 경우를 하나하나 다 체크하므로 길이가 길어질수록 각 사이클에서 시간이 기하급수적으로 늘어난다.

이 부분에 시간을 줄일 수 있는 방법을 생각해보다가, 같은 dial에 도착하는 경우는 그 이후로도 같이 움직이니 개별 계산보다 중첩하여 계산할수 있는 방향을 생각해보았다.

public int knightDialer3(int n) {

        if (n == 1) {
            return 10;
        }
        int[][] dials = { { 1, 2, 3 }, { 4, 5, 6, }, { 7, 8, 9 }, { -1, 0, -1 } };

        HashMap<Integer, ArrayList<Integer>> dialstoNextDial = new HashMap<>();

        for (int i = 0; i < dials.length; i++) {
            for (int j = 0; j < dials[i].length; j++) {
                if (dials[i][j] < 0) {
                    continue;
                }
                ArrayList<Integer> nextDials = checkAllNextDialPossible(dials, i, j);
                dialstoNextDial.put(dials[i][j], nextDials);

            }
        }
        int divideVal = 1000000007;
        int[][] dp = new int[n][10];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 10; j++) {
                if (i == 0) {
                    dp[i][j] = 1;
                } else {
                    if (dp[i - 1][j] > 0) {
                        ArrayList<Integer> nextDials = dialstoNextDial.get(j);
                        for (int t = 0; t < nextDials.size(); t++) {
                            int prevDialTime = nextDials.get(t);
                            dp[i][prevDialTime] = (dp[i][prevDialTime] + dp[i - 1][j]) % divideVal;
                        }
                    }
                }
            }

        }
        int sum = 0;
        for (int j = 0; j < 10; j++) {
            sum = (sum + dp[n - 1][j]) % divideVal;
        }

        return sum;
    }
    
    public ArrayList<Integer> checkAllNextDialPossible(int[][] dials, int i, int j) {

        ArrayList<Integer> nextDials = new ArrayList<Integer>();

        checkNextDialPossible(dials, i - 2, j + 1, nextDials);
        // -1 up + 2 right
        checkNextDialPossible(dials, i - 1, j + 2, nextDials);

        // 2 up + 1 right
        checkNextDialPossible(dials, i + 2, j + 1, nextDials);
        // 1 up + 2 right
        checkNextDialPossible(dials, i + 1, j + 2, nextDials);

        // -2 up - 1 right
        checkNextDialPossible(dials, i - 2, j - 1, nextDials);
        // -1 up - 2 right
        checkNextDialPossible(dials, i - 1, j - 2, nextDials);
        // 2 up - 1 right
        checkNextDialPossible(dials, i + 2, j - 1, nextDials);
        // 1 up - 2 right
        checkNextDialPossible(dials, i + 1, j - 2, nextDials);

        return nextDials;

    }

    public void checkNextDialPossible(int[][] dials, int horizonIdx, int verticalIdx,
            ArrayList<Integer> nextPossibleDials) {
        if (horizonIdx >= 0 && horizonIdx < dials.length && verticalIdx >= 0 && verticalIdx < dials[0].length) {
            int nextDial = dials[horizonIdx][verticalIdx];
            if (nextDial >= 0) {
                nextPossibleDials.add(nextDial);
            }
        }
    }