[LeetCode] 1765. Map of Highest Peak

https://leetcode.com/problems/map-of-highest-peak/description/

leetcode - Map of Highest Peak

문제 유형: bfs, 행렬

문제 난이도: Medium

 

문제

You are given an integer matrix isWater of size m x n that represents a map of land and water cells.

• If isWater[i][j] == 0, cell (i, j) is a land cell.
• If isWater[i][j] == 1, cell (i, j) is a water cell.

You must assign each cell a height in a way that follows these rules:

• The height of each cell must be non-negative.
• If the cell is a water cell, its height must be 0.
• Any two adjacent cells must have an absolute height difference of at most 1. A cell is adjacent to another cell if the former is directly north, east, south, or west of the latter (i.e., their sides are touching).

Find an assignment of heights such that the maximum height in the matrix is maximized.

Return an integer matrix height of size m x n where height[i][j] is cell (i, j)'s height. If there are multiple solutions, return any of them.

 

isWater라는 땅과 물의 정보를 담은 2D배열을 받는다.

isWater[i][j] == 0이라면, 땅이다. 1이면 물이ㅏ.

 

다음의 조건으로 높이 2D배열을 구성해야 한다:

• 높이는 음수가 될 수 없다.
• 물은 높이가 0이다.
• 두 인접한 셀의 최대 높이 차는 1이다.

높이를 최대화시킨 행렬을 반환하시오.

 

풀이

처음에는 매우높은 높이들로 가정시킨다.

isWater가 1인 곳들을 높이 0으로 한 뒤, 큐에 넣어서 bfs를 돌리면서, 인접한 높이가 현재 위치+1보다 높다면 현재 위치+1로 높이를 정상화하고, 큐에 넣어주면 된다.

bfs가 종료되면, 최대높이로 구성된 높이행렬이 완성된다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
private:
    vector<int> dx = {-1, 1, 0, 0};
    vector<int> dy = {0, 0, -1, 1};
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int n = isWater.size();
        int m = isWater[0].size();
        queue<pair<int, int>> q;
        vector<vector<int>> res(n, vector<int>(m, INT_MAX));
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                if(isWater[i][j]) {
                    q.push({i, j});
                    res[i][j] = 0;
                }
            }
        }

        while(!q.empty()) {
            auto curr = q.front();
            int x = curr.first;
            int y = curr.second;
            q.pop();

            for(int i = 0; i < 4; ++i) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                if(res[nx][ny] > res[x][y] + 1) {
                    res[nx][ny] = res[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }

        return res;
    }
};