[LeetCode] 2503. Maximum Number of Points From Grid Queries

https://leetcode.com/problems/maximum-number-of-points-from-grid-queries/description/

leetcode - Maximum Number of Points From Grid Queries

문제 유형: 우선순위 큐, bfs, 그리디

문제 난이도: Hard

 

원래 LeetCode문제를 leetcode solution탭에만 올리고 티스토리에 더 이상 안올리려 했는데..

앞으로 인상깊은 문제만 올리려합니다

 

문제 

You are given an m x n integer matrix grid and an array queries of size k.

Find an array answer of size k such that for each integer queries[i] you start in the top left cell of the matrix and repeat the following process:

• If queries[i] is strictly greater than the value of the current cell that you are in, then you get one point if it is your first time visiting this cell, and you can move to any adjacent cell in all 4 directions: up, down, left, and right.
• Otherwise, you do not get any points, and you end this process.

After the process, answer[i] is the maximum number of points you can get. Note that for each query you are allowed to visit the same cell multiple times.

Return the resulting array answer.

 

m x n의 정수 행렬 grid와 k개의 쿼리를 가진 queries배열이 주어집니다.

각각의 queries[i]에 대해서 맨 왼쪽 상단부터 시작해서 방문할 수 있는 칸들의 개수를 응답해야 합니다.

각 셀에서 상하좌우로 queries[i]보다 작은 칸에 이동할 수 있습니다.

이동할 수 없으면 이동을 멈풉니다.

(처음 숫자가 queries[i]보다 크면, 이동을 못합니다)

 

각각의 쿼리의 응답으로 answer를 담아서 반환하시오.

풀이

영문으로 보기:

https://leetcode.com/problems/maximum-number-of-points-from-grid-queries/solutions/6589438/priorityqueue-solution-easy-to-understan-0ffu/

 

각 쿼리에 대해 단순하게 계산하면 TLE에 걸린다.

대신, 우선순위 큐를 이용해서 가능한 모든 값을 모두 precompute해두면, 각각의 쿼리 응답을 O(1)에 처리할 수 있다.

 

• pq: 최소 힙(min-heap) 형태의 우선순위 큐.
  pq는 <gridNumber, row, col> 형태의 값을 저장한다.
• sizes: sizes[number]는 (grid의 시작 숫자가 number+1 이상일 때) 방문한 블록의 개수를 저장합니다.
• visited: (r, c) 위치를 이미 방문했는지를 저장하는 불리언 행렬.
• currMaxNum: 현재까지 최대 숫자를 추적합니다.
  currMaxNum보다 작은 숫자는 더 이상 sizes 배열을 업데이트하지 않는다.
• maxElem: 쿼리에서 사용할 최대 숫자 (즉, costs 배열의 길이).

 

1. maxElem 값을 구하고, sizes 배열을 초기화.
2. 우선순위 큐에 {grid[0][0], 0, 0}을 추가하여 탐색을 시작.
3. pq에서 하나씩 pop하며 (num, x, y)를 가져온다.
   • 만약 num > currMax라면:
     • sizes[currMax] 값을 sizes[currMax+1]로 전달.
     • currMax를 1 증가.
     • sizes[currMax] 값을 1 증가.
4. 현재 위치에서 방문하지 않은 인접 셀들을 확인하며:
   • (grid[nx][ny], nx, ny) 값을 큐에 삽입.
   • 해당 위치를 방문 처리.
5. currMax가 maxElem보다 작을 동안:
   • sizes[currMax] 값을 다음 인덱스로 전달
   • currMax++
6. 최종적으로 sizes 배열을 사용하여 쿼리들에 대한 답을 반환한다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = []() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    return 0;
}();
using tiii = tuple<int, int, int>;
class Solution {
    vector<int> dx = {-1, 1, 0, 0};
    vector<int> dy = {0, 0, -1, 1};

   public:
    vector<int> calc(vector<vector<int>>& grid, vector<int>& queries) {
        int n = grid.size();
        int m = grid[0].size();
        int maxElem = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] > maxElem) maxElem = grid[i][j];
            }
        }
        vector<int> sizes(maxElem + 1);

        vector<vector<bool>> visited(n, vector<bool>(m, false));
        priority_queue<tiii, vector<tiii>, greater<>> pq;
        pq.emplace(grid[0][0], 0, 0);
        visited[0][0] = true;
        int currMaxNum = 0;
        while (!pq.empty()) {
            int num, x, y;
            tie(num, x, y) = pq.top();
            pq.pop();

            int maxNum = max(num, currMaxNum);

            while (currMaxNum < maxNum) {
                sizes[currMaxNum + 1] = sizes[currMaxNum];
                currMaxNum++;
            }
            sizes[currMaxNum]++;

            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 || visited[nx][ny]) {
                    continue;
                }
                pq.emplace(grid[nx][ny], nx, ny);
                visited[nx][ny] = true;
            }
        }

        return sizes;
    }
    vector<int> maxPoints(vector<vector<int>>& grid, vector<int>& queries) {
        vector<int> sizes = calc(grid, queries);
        vector<int> res;
        int l = sizes.size();

        for (const auto& query : queries) {
            res.emplace_back(sizes[min(query - 1, l-1)]);
        }

        return res;
    }
};

 

Go

type Item struct {
	height int
	x      int
	y      int
}

type PriortiyQueue []Item

func (p PriortiyQueue) Len() int { return len(p) }
func (p PriortiyQueue) Less(i, j int) bool {
	if p[i].height == p[j].height {
		if p[i].x == p[j].x {
			return p[i].y < p[j].y
		}
		return p[i].x < p[j].x
	}
	return p[i].height < p[j].height
}
func (p *PriortiyQueue) Swap(i, j int) { (*p)[i], (*p)[j] = (*p)[j], (*p)[i] }

func (p *PriortiyQueue) Push(x interface{}) {
	*p = append(*p, x.(Item))
}

func (p *PriortiyQueue) Pop() interface{} {
	old := *p
	n := len(old)
	item := old[n-1]
	*p = old[0 : n-1]
	return item
}

type GridSolver struct {
	n       int
	m       int
	maxNum  int
	grid    [][]int
	queries []int
}

func NewGridSolver(grid [][]int, queries []int) *GridSolver {
	g := &GridSolver{
		n:       len(grid),
		m:       len(grid[0]),
		maxNum:  0,
		grid:    grid,
		queries: queries,
	}

	for _, row := range grid {
		for _, elem := range row {
			g.maxNum = max(elem, g.maxNum)
		}
	}

	return g
}

func (g *GridSolver) processGrid() []int {
	move := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
	res := make([]int, g.maxNum+1)
	visited := make([][]bool, g.n)
	for i, _ := range visited {
		visited[i] = make([]bool, g.m)
	}

	pq := make(PriortiyQueue, 0)
	heap.Init(&pq)
	heap.Push(&pq, Item{height: g.grid[0][0], x: 0, y: 0})
	visited[0][0] = true

	currMaxNum := 0
	for pq.Len() > 0 {
		item := heap.Pop(&pq).(Item)

		mx := max(currMaxNum, item.height)
		for currMaxNum < mx {
			res[currMaxNum+1] = res[currMaxNum]
			currMaxNum++
		}
		res[currMaxNum]++

		for _, mov := range move {
			nx := item.x + mov[0]
			ny := item.y + mov[1]

			if nx < 0 || ny < 0 || nx >= g.n || ny >= g.m || visited[nx][ny] {
				continue
			}
			heap.Push(&pq, Item{height: g.grid[nx][ny], x: nx, y: ny})
			visited[nx][ny] = true
		}
	}

	for currMaxNum < g.maxNum {
		res[currMaxNum+1] = res[currMaxNum]
		currMaxNum++
	}

	return res
}

func maxPoints(grid [][]int, queries []int) []int {
	g := NewGridSolver(grid, queries)
	responses := g.processGrid()
	ans := make([]int, len(queries))
    l := len(responses)

	for i, query := range queries {
		ans[i] = responses[min(query-1, l-1)]
	}

	return ans
}