[LeetCode] 329. Longest Increasing Path in a Matrix

문제 URL :https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

Longest Increasing Path in a Matrix - LeetCode

 

접근법: 2차원배열에서 자신보다 큰숫자를 넘어갈수있을때

그경로에서 가장긴 경로를 찾는문제입니다.

 

2가지 풀이가 가능합니다.

방법 1:

처음 풀었을땐 다익스트라처럼 이용하게 풀게됐습니다.

모든 경로의 시작점의 길이를 1로 정하고 시작하고 근처에 자신보다 큰 숫자가 있고

거리가 길어지는대로 탐색을 시작합니다.

 

소스코드 1:             

class Solution {
public:

int check[200][200];
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};
int n,m;
bool isrange(int y,int x){
    return 0<=y&&y<n&&0<=x&&x<m;
}
int dijkstra(vector<vector<int>>& matrix){
    priority_queue<tuple<int,int,int,int>> pq;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            pq.push({-1,-matrix[i][j],i,j});
            check[i][j]=1;
        }
    }
    int res =0;
    while(!pq.empty()){
        int dis,num,y,x;
        tie(dis,num,y,x)=pq.top();
        
        dis=-dis;
        num=-num;
        pq.pop();
        res=max(res,dis);
        if(check[y][x]>dis)continue;
        for(int i=0;i<4;i++){
            int ny=y+dy[i];
            int nx=x+dx[i];
            int ndis = dis+1;
            if(isrange(ny,nx)&&num<matrix[ny][nx]){
                if(ndis>check[ny][nx]){
                    pq.push({-ndis,-matrix[ny][nx],ny,nx});
                    check[ny][nx]=ndis;
                }
            }
        }
    }
    return res;
}
int longestIncreasingPath(vector<vector<int>>& matrix) {
    int res=0;
    n=matrix.size();
    m=matrix[0].size();

    return dijkstra(matrix);
}
};

                   

방법 2: dfs를 이용하여 메모이제이션 기법으로 더 빠르게 풀수도있습니다.

 

소스코드 :

class Solution {
public:

int dp[200][200];
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};
int n,m;
bool isrange(int y,int x){
    return 0<=y&&y<n&&0<=x&&x<m;
}
int dfs(vector<vector<int>> &matrix,int y,int x){
    int &cache=dp[y][x];
    if(cache!=-1)return cache;
    cache=1;
    for(int i=0;i<4;i++){
        int ny=y+dy[i];
        int nx=x+dx[i];
        if(isrange(ny,nx)&&matrix[y][x]<matrix[ny][nx]){
            cache=max(cache,dfs(matrix,ny,nx)+1);
        }
    }
    return cache;
}
int longestIncreasingPath(vector<vector<int>>& matrix) {
    int res=0;
    n=matrix.size();
    m=matrix[0].size();
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(dp[i][j]==-1){
                res=max(res,dfs(matrix,i,j));
            }
        }
    }
    return res;
}
};

                                                                         

궁금한전 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.