[C] LeetCode 329. Longest Increasing Path in a Matrix

문제

번역

m by n 정수 배열 matrix가 주어진다.

이때 matrix에서 가장 긴 증가하는 길의 길이를 반환해라.

각 셀에서, 우리는 상하좌우로만 움직일 수 있다. 대각선으로 움직이거나 경계 밖으로 나갈 수는 없다.

접근 방법 및 소스코드

Hard 단계라서 처음에 조금 두려웠는데, 생각보다 쉽게 풀렸다.

DP를 사용한 풀이로 접근하면 된다.

 

각 칸을 그래프의 노드로 보고 상하좌우 중 현재 값보다 큰 값을 갖는 노드로 이동한다.

DFS를 통해 해당 칸에서 시작하는 최대 증가 경로 길이를 위해 자신을 기준으로 해 상하좌우 노드를 탐색한다.

같은 칸의 결과를 재계산하지 않도록 DP를 통해 저장하고 재사용한다(메모이제이션 기법)

 

이를 코드로 구현하면 다음과 같이 작성할 수 있다.

 

int m,n;
int dr[4] = {-1,1,0,0}, dc[4]= {0,0,-1,1};
int dp[200][200];
int** gmatrix;

int dfs(int r, int c) {
    if(dp[r][c] != 0) return dp[r][c];
    dp[r][c]=1;
    
    for(int i=0;i<4;i++){
        int nr = r + dr[i];
        int nc = c + dc[i];
        if(nr <0 || nr >= m || nc < 0 || nc >= n) continue;
        if(gmatrix[nr][nc] > gmatrix[r][c]) {
            int t = 1+dfs(nr,nc);
            dp[r][c] = (dp[r][c] < t) ? t : dp[r][c];
        }
    }
    return dp[r][c];
}

int longestIncreasingPath(int** matrix, int matrixSize, int* matrixColSize) {
    m = matrixSize; n = matrixColSize[0];
    memset(dp, 0, sizeof(dp)); gmatrix=matrix;
    int ans=0;
    for(int i=0; i<m;i++) {
        for(int j=0;j<n;j++) {
            int t = dfs( i, j);
            ans = (ans < t) ? t : ans;
        }
    }
    return ans;
}