LeetCode 329. Longest Increasing Path in a Matrix

Longest Increasing Path in a Matrix - LeetCode

 

문제 설명

2차원 행렬이 주어졌을 때 행렬에서 가장 긴 증가하는 경로의 길이를 구하시오

입력: matrix = [[9,9,4],[6,6,8],[2,1,1]]
출력: 4

 

입력: matrix = [[1,2,3],[2,1,4],[7,6,5]]
출력: 7

 

 

문제 풀이

처음에 일반 bfs로 푸는 것을 생각했음 그러나 이 문제에서 시작점은 여러 개가 될 수 있고 모든 칸이 시작점이 될 수 있으므로 각 칸마다 bfs를 반복해서 문제를 풀면 시간 초과가 날 것이라고 예상

 

그런데 이제, 각 칸을 하나의 노드라고 생각한다면 현재 칸에서 상하좌우로 이동할수 있고, 

이때 인접한 칸들 사이에서 값이 작은 칸에서 큰 칸으로 간선을 연결한다면 증가 경로를 가지는 방향 그래프로 표현할 수 있음

모든 간선은 작은 값에서 큰 값으로 향하기 때문에 경로를 따라갈수록 값이 계속 증가하므로 이는 위상정렬에서 중요한 사이클이 발생하지 않아야 한다 라는 조건을 만족함.

 

여기서 위상정렬에서는 모든 시작점을 각각 탐색 하는 대신 진입 차수가 0인 칸들을 증가 경로의 시작점으로 보고 한꺼번에 큐에 넣어 처리할 수가 있음. 이후 위상 정렬을 레벨 단위로 진행하면 여러 시작점에서 출발하는 증가 경로를 동시에 탐색하면서도 각 칸을 한 번씩만 처리가 가능하다.

또한 위상 정렬의 각 레벨은 경로의 한 스텝을 의미하므로 전체 레벨의 수를 세면 최장 증가 경로의 길이를 구할 수 있음.

여러 시점에서 bfs반복하며 여러번 도는 것보다는 모든 증가 경로를 한 번에 계층적으로 처리할 수 있는 위상 정렬을 사용해서 문제를 풂.

 

class Solution {
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int y=matrix.size();
        int x=matrix[0].size();
        int minDist=0;
        int indegree[101][101]={};
        queue<pair<int,int>> q;

        //각 칸의 진입 차수를 계산함.
        for(int i=0;i<y;i++)
        {
            for(int j=0;j<x;j++)
            {
                for(int dir=0;dir<4;dir++)
                {
                    int ny=i+dx[dir];
                    int nx=j+dy[dir];
                    if(ny<0||nx<0||nx>=x||ny>=y) continue;
                    if(matrix[ny][nx]<matrix[i][j])
                    //작은 칸에서 큰 값의 방향으로 간선을 연결한다고 가정
                    //인접한 칸의 값이 더 작다면 현재 칸의 진입할 수 있다는 뜻이므로
                    //해당 칸의 진입 차수를 증가시킴.
                    {
                        indegree[i][j]++;
                    }
                }
            }
        }
        //맨 처음 진입 차수가 0인 곳부터 시작
        for(int i=0;i<y;i++)
        {
            for(int j=0;j<x;j++)
            {
                if(indegree[i][j]==0)
                {
                    q.push({i,j});
                }
            }
        }
        while(!q.empty())
        {
            int size=q.size();
            minDist++;
            while(size--)
            {
                pair<int ,int> cur=q.front();
                int curX=cur.second;
                int curY=cur.first;
                q.pop();
                
                for(int i=0;i<4;i++)
                {
                    int nextX=curX+dx[i];
                    int nextY=curY+dy[i];
                    if(nextX<0||nextY<0||nextX>=x||nextY>=y)continue;
                    if(matrix[nextY][nextX]>matrix[curY][curX])
                    //현재 칸 보다 값이 큰 곳으로만 이동하여 
                    //다음 칸의 진입 차수를 감소 시키면서 이동
                    {
                        indegree[nextY][nextX]--;
                        if(indegree[nextY][nextX]==0)
                        {
                            q.push({nextY,nextX});
                        }
                    }

                }

            }

        }
        return minDist;

    }
};

 

 

글 내용 중에 틀린 것이 있거나 궁금한 것이 있다면 댓글 남겨주세요! 봐주셔서 감사합니다.