[LeetCode] 1765. Map of Highest Peak (Python)

 

 

난이도: 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.

 

문제 예제

---

Example 1:

Input: isWater = [[0,1],[0,0]]
Output: [[1,0],[2,1]]
Explanation: The image shows the assigned heights of each cell. The blue cell is the water cell, and the green cells are the land cells.

Example 2:

 

Input: isWater = [[0,0,1],[1,0,0],[0,0,0]]
Output: [[1,1,0],[0,1,1],[1,2,2]]
Explanation: A height of 2 is the maximum possible height of any assignment.
Any height assignment that has a maximum height of 2 while still meeting the rules will also be accepted.

 

제한 사항

---

• m == isWater.length
• n == isWater[i].length
• 1 <= m, n <= 1000
• isWater[i][j] is 0 or 1.
• There is at least one water cell.

Note: This question is the same as 542: https://leetcode.com/problems/01-matrix/

 

Solution(솔루션)

---

class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        n = len(isWater)
        m = len(isWater[0])
        answer = [[0 for _ in range(m)] for _ in range(n)]
        visited = [[False for _ in range(m)] for _ in range(n)]
        q = deque([])
        
        for i in range(n):
            for j in range(m):
                if isWater[i][j] == 1:
                    q.append((i, j))
                    visited[i][j] = True
        
        moves = [[0, 1], [0, -1], [1, 0], [-1,0]]

        while q:
            x, y = q.popleft()

            for move in moves:
                nx = x + move[0]
                ny = y + move[1]

                if 0<= nx < n and 0 <= ny < m and not visited[nx][ny]:
                    visited[nx][ny] = True
                    answer[nx][ny] = answer[x][y] + 1
                    q.append((nx, ny))
        
        return answer

 

간단한 BFS 문제였다.

 

isWater 크기와 같은 answer를 만들고 0으로 채워주었다.

 

다음으로 water의 위치를 q에 저장하고 방문 체크를 해주었다.

 

이제 q가 빌때까지, q에서 popleft한 위치의 상하좌우 값에 +1을 해주고 q에 좌표를 넣어주었고, 방문 체크도 해주었다.

 

이런식으로 q가 빌때까지 반복했고, 마지막에 answer를 반환하여 정답을 맞출 수 있었다.

---

문제: 1765. Map of Highest Peak

 

깃허브: github

algorithmPractice/LeetCode/1876-map-of-highest-peak at main · laewonJeong/algorithmPractice