[Leetcode]935. Knight Dialer

문제 요약

• 알고리즘 분류:동적계획법(DP)
• 난이도: Medium
• 문제내용:
  • 나이트는 체스의 이동처럼 같다
  • 나이트는 체스판이 아닌 계산기에서 이동한다.(단 *, # 이동 불가능이다.)
  • 0~9에서 아무대나 시작한다고 했을때 이동횟수가 n을 주어 졌을때 나올수 있는 경우의 수를 반환 하여라.
• 사이트 주소: https://leetcode.com/problems/knight-dialer/description/

문제풀이

 이번 문제는 나이트 이동때문에 백트레킹이라고 볼수 있지만 n이 5000인점을 보면 백트레킹으로 풀면 시간 초과로인하여 완전 탐색같은 알고리즘으로는 하기는 그렇다. 그래서 최적화 할 수  있는 동적 계획법을 해야 한다. 동적계획법에 대한 설명은 아래글에서 확인해보면 된다.

https://jih3508.tistory.com/89

[알고리즘 이론] 동적계획법(Dynamic Programming, DP)

문제 접근방법

DP(Dynamic Programming) 문제의 해결은 주로 구현보다는 문제 해결에 필요한 아이디어를 요구한다. 그래서 어떻게 점화식으로 만들어야 할지 고민을 해야 한다. 일단 0~9이동 가능한다는 점부터 보면 이동 할수 있는 위치는 몇개 없다는 점 부터 봐야 한다. 0~9부터 이동할 수 있는 위치는 아래 내용 보면 된다.

0: [4, 6]
1: [6, 8]
2: [7, 9]
3: [4, 8]
4: [3, 9, 0]
5: [],
6: [1, 7, 0]
7: [2, 6]
8: [1, 3]
9: [2, 4]

 다시 DP 점화식을 세우는 방식을 보겠다. 일단 8×8 체스판이 아닌 계산기이고 이동할수 있는 범위도 한정적인것 부터 봐야한다.  그리고 범위도 10개 정도 라서 0~9까지 범위안에 돌면서 점화식을 세우면 된다. 

일단 n이 1부터 보면 0~9까지 각자리에 두면 된다. 하지만 n이 2부터 5가 이동할수 있는 위치가 없고 다른데에서 도착하는 번호도 아니라서 5를 제외해서 점화식을 짜는 구조를 만들어야 한다. 그래서 0~9까지 시작해서 최종까지 나가는 경우의 수를 각각 구해서 나가는 식으로 진행해야하고 점화식을 다 구하고 0~9를 다 더하는 식으로 진행 해야 한다. 점화식 구조는 아래처럼 작성하면된다.

1. i는 이동횟수, j는 다이얼리 번호, k는 j지점에서 이동한 지점이라고 가정한다.
2. dp[0] = dp[1] = dp[2] .... = dp[9] = 1
3. dp[i][k] = dp[i][k] + dp[i-1][j]
4. dp[n] = dp[n][0] + dp[n][1] + ... + dp[n][9]

 1번은 위치만 하면되기때문에 모든 번호에 다 위치 할수 있으므로 1로 지정하면된다.

 3번 보면 점화식이 복잡해 보일수 있는데 간단하게 생각해볼수 있다. j지점에서 다음으로 갈수 있는지점을 더한다고 보면되고 그리도 k도착하는게 이전에 지점으로 부터 온것이 1개가 아닌 몇개가 될수 있어서 이전 으로 부터 온것을 누적한다고 보면 된다. 그리고 점화식을 다 구하면 n번째 길이부분을 다 더하면된다.  그리고 1_000_000_007나눈 나머지 구하는것까지 하면 끝이다.

 이렇게 구현하면 시작복잡도는 O(N^2)으로 볼수 있다. 그 이유는 n개 길이 만큼 0~9까지 각각 탐색하고나고 그 다음 이동하는 지점까지 가다보니 N^2만큼 나온다고 볼수있다.

 

Code

Python

class Solution:
    def knightDialer(self, n: int) -> int:
        movePoints = {
            0: [4, 6],
            1: [6, 8],
            2: [7, 9],
            3: [4, 8],
            4: [3, 9, 0],
            5: [],
            6: [1, 7, 0],
            7: [2, 6],
            8: [1, 3],
            9: [2, 4]
        }
        MOD = 1e9 + 7 # 나머지 연산 수

        dp = [[0] * 10 for _ in range(n)]
        dp[0] = [1] * 10
        for i in range(n-1):
            # 0 ~ 9까지 탐색
            for j in range(10):
                # 이동할 지점에 추가
                for point in movePoints[j]:
                    dp[i+1][point] = (dp[i+1][point] + dp[i][j]) % MOD
        
        # 결과 0 ~ 9까지 경우의 수 더하기
        return int(sum(dp[n-1]) % MOD)

 

Java

java같은 정적 변수선언하는 언어는 Int형으로 계산하기에는 범위가 넘어가서  long으로 계산후에 끝에 typecasting으로 integer형으로 변환시키는 작업을 해야한다.

class Solution {
     // 이동 가능한 지점
    int[][] movePoints = {
            {4, 6}, // 0
            {6, 8}, // 1
            {7, 9}, // 2
            {4, 8}, // 3
            {3, 9, 0}, // 4
            {}, // 5
            {1, 7, 0}, // 6
            {2, 6}, // 7
            {1, 3}, // 8
            {2, 4} // 9
    };

    long MOD = (int) Math.pow(10, 9) + 7; // 나머지 연산 수

    public int knightDialer(int n) {

        long[][] dp = new long[n][10];

        Arrays.fill(dp[0], 1);

        for (int i = 0; i < n - 1; i++) {
            // 0 ~ 9까지 탐색
            for(int j = 0; j < 10; j++){
                // 이동할 지점에 추가
                for(int num: movePoints[j]){
                    dp[i+1][num] = (dp[i+1][num] +  dp[i][j]) % MOD;
                }
            }

        }
        // 마지막 이동가능한 모든수 구하기
        long result = 0;
        for (int i = 0; i < 10; i++){
            result = (result + dp[n-1][i]) % MOD;
        }

        return (int) result;
    }
}