[Leetcode] 2435. Paths in Matrix Whose Sum Is Divisible by K

방법1. BFS

모든 경로를 한 번은 돌아야 하므로 BFS로 접근해봤다. 어쨌든 전부 계산을 해봐야하고 제한조건이 1 <= m, n <= 5 * 10^4 이니까 통과할 수 있지 않을까 싶었다. 그리고 처참히 시간초과가 떴다.

곰곰히 생각해 본 결과, 우선 문제를 해결하기 위해서는 무조건 모든 경로에 대해 매트릭스의 우하단까지 계산을 해야 하는 것은 당연한 사실이다. 그렇다면 한 지점에 도달하는 방법의 갯수만큼 노드가 생성되는 BFS의 방식이 시간초과의 원인이라고 생각되었다.

그렇다면 남은 답은 동적프로그래밍 밖에 없다. 다행히 며칠전에 비슷한 문제인 3으로 나누어 떨어지는 가장 큰 합을 풀었어서 k 의 최댓값을 확인해보니 50으로 크지 않아 가능하겠다 싶었다.

const MODULO = 1000000000 + 7;

function numberOfPaths(grid: number[][], k: number): number {
    const RR = grid.length;
    const CC = grid[0].length;

    const q = new MyQueue();

    let count = 0;

    const node = new Node({ r: 0, c: 0, sum: (grid[0][0] % k), times: 0 });

    q.put(node);

    while (q.length !== 0) {
        const { r, c, times, sum } = q.pop();


        // if (times > k && sum !== 0) {
        //     continue;
        // }

        if (r === (RR - 1) && c === (CC - 1) && sum === 0) {
            count = (count + 1) % MODULO;
        }

        if (r + 1 < RR) {
            const newNode = new Node({
                r: r + 1,
                c,
                times: times + 1,
                sum: (sum + grid[r + 1][c]) % k
            })

            q.put(newNode);
        }

        if (c + 1 < CC) {
            const newNode = new Node({
                r: r,
                c: c + 1,
                times: times + 1,
                sum: (sum + grid[r][c + 1]) % k
            })

            q.put(newNode);
        }
    }

    return count;
};

class Node {
    next: null | Node = null;
    value: {
        times: number,
        sum: number,
        r: number,
        c: number,
    } = { r: 0, c: 0, sum: 0, times: 0 };

    constructor({ r, c, sum, times }: { r: number, c: number, times: number, sum: number }) {
        this.value.r = r;
        this.value.c = c;
        this.value.sum = sum;
        this.value.times = times;
    }
}

class MyQueue {
    head = null;
    tail = null;
    length = 0;

    put(node: Node) {
        const currentTail = this.tail;

        if (currentTail != null) {
            currentTail.next = node;
        }

        this.tail = node;

        if (this.head == null) {
            this.head = node;
        }

        this.length += 1;
    }

    pop() {
        const currentHead = this.head;

        if (currentHead == null) {
            this.tail = null;
            return null;
        }

        this.head = currentHead.next;

        this.length -= 1;

        return currentHead.value;
    }

    peek() {
        return this.head.value;
    }
}

방법2. Dynamic Programming

한 지점에 도달하는 방법은 1. 위에서 내려오기 2. 왼쪽에서 오른쪽으로 오기 두 가지 뿐이다. 매트릭스의 모든 셀에 대해 k의 길이를 가지는 메모이제이션 배열을 만들고 grid[0][0] % k 의 값을 시작점에 넣어준 뒤 2중 포문을 돌렸다.

어차피 모듈로연산은 덧셈의 분배법칙이 성립하기에 한번에 위쪽과 왼쪽의 합을 구할 필요는 없다. 경계조건을 잘 따라가면서 위쪽으로부터 내려오는 값, 왼쪽에서 들어오는 값을 따로 계산해주었다.중간에 MODULO 라는 나누는 값도 있어서 메모이제이션의 인덱스로 쓰이는 모듈로 연산의 결과값들과 살짝 헷갈렸으나 괜찮았다.

const MODULO = 1000000000 + 7;

function numberOfPaths(grid: number[][], k: number): number {
    const RR = grid.length;
    const CC = grid[0].length;

    const dp = Array.from({
        length: RR
    },
        () => Array.from({
            length: CC
        },
            () => Array.from({
                length: k
            },
                () => 0)
        )
    )

    dp[0][0][grid[0][0] % k] = 1;

    for (let r = 0; r < RR; r++) {
        for (let c = 0; c < CC; c++) {
            for (let prevR = 0; prevR < k; prevR++) {
                const nextR = (grid[r][c] + prevR) % k;
                
                if (r !== 0 && dp[r - 1][c][prevR] !== 0) {
                    dp[r][c][nextR] = (dp[r][c][nextR] + dp[r - 1][c][prevR]) % MODULO;
                }

                if (c !== 0 && dp[r][c - 1][prevR] !== 0) {
                    dp[r][c][nextR] = (dp[r][c][nextR] + dp[r][c - 1][prevR]) % MODULO;
                }
            }
        }
    }

    return dp[RR - 1][CC - 1][0]
};

나머지가 0 인(나누어 떨어지는) 경로의 합만 보여주면 되므로 메모이제이션 배열의 0번째 값을 반환하면 된다.