[알고리즘] LeetCode 1102번 "Path With Maximum Minimum Value" (C/C++) - Don 임베디드

문제요약:

Given an M x N integer matrix, return the maximum bandwidth of a path starting at (0,0) and ending at (M-1, N-1) moving in the 4 cardinal direstions.

 

The maximum bandwidth of a path is the minimum value in that path.

 

제약:

M == Row

N == Column

1 <= M, N <= 100

0 <= grid[i][j] <= 10^9

 

예제 1 입력.	예제 1 출력.
grid = [[5,4,5],  [1,2,6],  [7,4,6]]	4
예제 2 입력.	예제 2 출력.
grid = [[2,2,1,2,2,2],  [1,2,2,2,1,2]]	2
예제 3 입력.	예제 3 출력.
grid = [[3,4,6,3,4],  [0,2,1,1,7],  [8,8,3,2,7],  [3,2,4,9,8],  [4,1,2,0,0],  [4,6,5,4,3]]	3

 

 

정답코드:

class Solution {
public:
    enum Direction { DOWN=0, RIGHT=1, UP=2, LEFT=3};
    enum TmpEnum { X_LOC=0, Y_LOC=1, VAL=2};
 
    int maximumMinimumPath(vector<vector<int>>& grid) {
        
        int goalX = grid.size() - 1;
        int goalY = grid[0].size() - 1;
        int curMin = INT_MAX;
        int curX, curY;
        int newX, newY;
        bool bPathFound = false;
 
        vector<vector<bool>> visited(grid.size(), vector<bool> (grid[0].size(), false));
 
        // down right up left
        int dx[4] = {1,0,-1,0};
        int dy[4] = {0,1,0,-1};
 
        // declare a priority queue
        priority_queue<pair<int, pair<int, int>>> maxQ;
        maxQ.push({grid[0][0], {0, 0}});
 
        while (!maxQ.empty() && !bPathFound)
        {
            curX = maxQ.top().second.first;
            curY = maxQ.top().second.second;
            int curVal = maxQ.top().first;
            
            // pop
            maxQ.pop();
 
            // update min
            curMin = min(curMin, curVal);
 
            // check if it reached the goal
            if (curX == goalX && curY == goalY)
            {
                bPathFound = true;
                break;
            }
 
            // push all four adjacent steps
            for (int i = 0; i < 4; i++)
            {
                newX = curX + dx[i];
                newY = curY + dy[i];
                if(0 <= newX && newX <= goalX && 0 <= newY && newY <= goalY
                && visited[newX][newY] == false)
                {
                    maxQ.push({grid[newX][newY], {newX, newY}});
                }
            }
            // mark as visited
            visited[curX][curY] = true;
        }
 
        if(!bPathFound) return -1;  // error case
 
        // return result
        return curMin;
    }
};

핵심 Idea:

Priority Queue + BFS (Dijkstra's algorithm)

=> 현재 Queue에 있는 Node들 중 가장 bandwidth 값이 큰 노드를 선택한다.

=> (*proof 생략)

=> Path를 구한 뒤, Parent를 tracking 하면서 다시 계산할 필요가 없이,

     Node를 Pop 할 때마다 Min 값을 계속해서 업데이트 하면 된다.

 

원본 링크: https://leetcode.com/problems/path-with-maximum-minimum-value/description/

 

 

*Reference:

Texas A&M University - Fall 2022 CSCE 629 (Dr. Jianer Chen)

Course Notes 5. The Maximum Bandwidth Path

https://people.engr.tamu.edu/j-chen3/courses/629/2022/Lectures/notes3.pdf