[LeetCode] DFS-BFS 329. Longest Increasing Path in a Matrix

문제

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

 

Example 1:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Example 3:

Input: matrix = [[1]]
Output: 1

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• 0 <= matrix[i][j] <= 231 - 1

---

문제풀이

- Memoization

- DFS(재귀함수)

 

- matrix[0][0] = 9에서 위 아래 왼쪽 오른쪽 탐험 시작

const top = dfs(row - 1, col, nodeVal);
const bottom = dfs(row + 1, col, nodeVal);
const left = dfs(row, col - 1, nodeVal);
const right = dfs(row, col + 1, nodeVal);

- 위에는 아무것도 없으므로 length는 0으로 리턴

const top = dfs(row + 1, col, nodeVal) = 0

- 아래에는 6이 있고 현재 value(6)가 이전 value(9) 보다 작으므로 => length를 이룰 수 있음

- 6을 중심으로 위, 아래, 왼쪽, 오른쪽을 탐험 시작

...

- 현재 값(1)이 이전 value(2)보다 작으므로 length를 이룰 수 있음

- 1을 중심으로 위, 아래 왼쪽 오른쪽 탐험시작

 

- 위: 현재값 6은 이전 값 1보다 크므로 length에 포함될 수 없음

- 아래: 없음

- 왼쪽: 현재값 2는 이전값 1보다 크기 때문에 length에 포함될 수 없음

- 오른쪽: 현재값과 이전값이 동일하므로 length에 포함될 수 없음

 

함수를 다 타고 갔으니 이제 스택의 윗 함수로 이동하자.

 

...

 

// length = index + 1

const maxLength = Math.max(top, bottom, left, right) + 1;
const saveLength = map.set(`${row},${col}`, maxLength);

 

이렇게 되면 메모이제이션한 객체안에는 다음과 같은 것들이 적힌다.

{
    ['0,0']: 4,
    ['1,0']: 3,
    ['2,0']: 2,
    ['2,1']: 1,
}

 

...

이러저러하다가

for loop이 다돌면 maxLength = 4가 됨

 

재귀함수를 이용해서 위 아래 왼쪽 오른쪽 왔다갔다 하는걸 이해하는게 가장 중요함

---

코드

// DFS

var longestIncreasingPath = function(matrix) {
    let maxLength = 0;
    
    const width = matrix[0].length - 1;
    const height = matrix.length - 1;
    const map = new Map();
    
    function dfs(row, col, prev) {
        const KEY = `${row},${col}`;
        
        if(row < 0 || col < 0 || row > height || col > width) {
            return 0;
        }
        
        const nodeVal = matrix[row][col];
        
        if(nodeVal >= prev) return 0
        
        if(!map.has(KEY)) {
            const top = dfs(row - 1, col, nodeVal);
            const bottom = dfs(row + 1, col, nodeVal);
            const left = dfs(row, col - 1, nodeVal);
            const right = dfs(row, col + 1, nodeVal);   
            
            const curMaxLength = Math.max(top, bottom, left, right) + 1
            
            map.set(KEY, curMaxLength);
        }
        
        return map.get(KEY);
    }
    
    for(let row = 0; row <= height; row++) {
        for(let col = 0; col <= width; col++) {
            maxLength = Math.max(dfs(row, col, Infinity), maxLength);
        }
    }
    
    return maxLength;
}

 

참고

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/discuss/2187695/JS-or-Visualised-or-DFS-and-Memoization