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

바쁜 일정으로 챌린지를 못하다가 금요일 문제를 풀어보려 하니 Hard🎉 난이도인거 아니겠어요.
저도 시간 제한으로 문제를 틀려버러셔 이번 문제는 해당 문제에 대한 좋은 알고리즘들을 총정리 하는 시간을 갖도록 하겠습니다✨

https://leetcode.com/problems/maximum-number-of-points-from-grid-queries/description/?envType=daily-question&envId=2025-03-28

 

문제

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.


Constraints:

m == grid.length
n == grid[i].length
2 <= m, n <= 1000
4 <= m * n <= 105
k == queries.length
1 <= k <= 104
1 <= grid[i][j], queries[i] <= 106

Input: grid = [[1,2,3],[2,5,7],[3,5,1]], queries = [5,6,2]
Output: [5,8,1]
Explanation: The diagrams above show which cells we visit to get points for each query.

1. 가장 기초적인 접근법

이미지상 제일 왼쪽 셀을 기준으로 queries 에 주어진 값보다 작은 값을 가진 인접한 셀을 방문하는 문제입니다!
기본적으로 문제에서 주어진 내용을 기준으로 판단해본다면,

• 상,하,좌,우 기준으로 인접한 셀의 값이 쿼리 값보다 적다면 연결 가능
• 처음 방문하는 셀, 즉 쿼리값보다 적은 이접한 셀의 수

위 두가지 내용을 기반으로 첫번째 풀이법을 고민했고, BFS 경로로 탐색하기로 생각했어요!

BFS 로 경로 탐색하기

🤖 BFS 알고리즘 분석

너비 우선 탐색(Breadth-First Search, BFS)은 그래프나 트리를 탐색하는 대표적인 알고리즘입니다. 마치 물결이 넓게 퍼져나가듯이 가까운 노드부터 순서대로 탐색하는 방식이죠!

동작 설명

1. 방문 여부를 추적할 visited 배열 생성
2. 시작점 (0,0) 큐에 추가
3. 큐가 빌때 까지 큐의 첫번째 요소를 보고, 판단하여 인접한 점을 다시 큐에 추가
4. 큐가 비는 시점에 탐색 완료

코드

func maxPoints(grid [][]int, queries []int) []int {
    m, n := len(grid), len(grid[0])
    directions := [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

    answer := make([]int, len(queries))

    for i, query := range queries {
        visited := make([][]bool, m)
        for j := range visited {
            visited[j] = make([]bool, n)
        }

        queue := list.New()
        queue.PushBack([]int{0, 0})
        visited[0][0] = true
        points := 0

        visitedCells := [][]int{}

        for queue.Len() > 0 {
            curr := queue.Front().Value.([]int)
            queue.Remove(queue.Front())

            if grid[curr[0]][curr[1]] < query {
                if !contains(visitedCells, curr) {
                    points++
                    visitedCells = append(visitedCells, curr)
                }

                for _, dir := range directions {
                    newX, newY := curr[0]+dir[0], curr[1]+dir[1]

                    if newX >= 0 && newX < m && newY >= 0 && newY < n && 
                       !visited[newX][newY] && grid[newX][newY] < query {
                        queue.PushBack([]int{newX, newY})
                        visited[newX][newY] = true
                    }
                }
            }
        }

        answer[i] = points
    }

    return answer
}

func contains(cells [][]int, cell []int) bool {
    for _, c := range cells {
        if c[0] == cell[0] && c[1] == cell[1] {
            return true
        }
    }
    return false
}

결과

타임 아웃이 발생해 실패했습니다 😂
Hard 난이도인 만큼 단순한 알고리즘 풀이만으로는 시간내 통과가 안되는 Constraints 가 설정된 것이 문제인데요. 그럼 어떤 더 좋은 방법들이 있는지 계속해서 알아보겟습니다.

2. 탐색 순서와 방법을 정렬하여, 경로찾는 과정을 공유하기!

이전에 풀이인 BFS 풀이 방법은 주어진 queries 배열의 요소마다 매번 경로를 찾는 방식의 풀이였는데요.
queries 의 값을 sorting 하고, 기존의 Queue 대신 minHeap 을 사용하여 매번의 경로 찾기를 반복하면서 중복되어 탐색하는 부분을 공유하는 방법으로 기존 문제의 풀이를 최적화를 진행해보겠습니다!

동작 설명

1. queries 를 오름차순으로 정렬 (정답 제출 순서는 맞추기 위해 index를 함께 따로 저장)
2. queries 를 query 요소보다 작은 값들을 순회하며 BFS 진행,
3. BFS 순회가 끝나는 순간, 해당 query 요소 인덱스로 답을 기록한 후 다음 qeuries 요소 값 (더 큰 값) 으로 변경하여 탐색 재시도
4. 모든 queries 순회가 종료하면 기록된 답을 제출

**여기서 minHeap 을 BFS 를 위한 자료구조로 사용하였기 때문에, queries 배열에 대한 순회의 1차수가 끝난다면 다음 행선지 후보는 현재 판단해야하는 셀의 값중 가장 최솟값을 보장하기 때문에 모든 경로 탐색마다 동일한 경로 탐색을 보장하게 된답니다.

코드

import (
    "container/heap"
    "sort"
)

type Cell struct {
    val, x, y int
}

type MinHeap []Cell

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].val < h[j].val }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(Cell)) }
func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func maxPoints(grid [][]int, queries []int) []int {
    m, n := len(grid), len(grid[0])

    // 쿼리와 인덱스 저장
    queryWithIndex := make([][2]int, len(queries))
    for i, q := range queries {
        queryWithIndex[i] = [2]int{q, i}
    }

    // 쿼리 정렬
    sort.Slice(queryWithIndex, func(i, j int) bool {
        return queryWithIndex[i][0] < queryWithIndex[j][0]
    })

    // 방문 배열과 결과 배열 초기화
    visited := make([][]bool, m)
    for i := range visited {
        visited[i] = make([]bool, n)
    }

    result := make([]int, len(queries))

    // 우선순위 큐 초기화
    h := &MinHeap{{grid[0][0], 0, 0}}
    heap.Init(h)
    visited[0][0] = true

    // 방향 벡터
    dirs := [][]int{{0,1}, {1,0}, {0,-1}, {-1,0}}

    points := 0
    for _, queryInfo := range queryWithIndex {
        query, idx := queryInfo[0], queryInfo[1]

        // 현재 쿼리보다 작은 값들 탐색
        for h.Len() > 0 && (*h)[0].val < query {
            curr := heap.Pop(h).(Cell)
            points++

            // 인접 셀 탐색
            for _, dir := range dirs {
                nx, ny := curr.x + dir[0], curr.y + dir[1]

                if nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] {
                    heap.Push(h, Cell{grid[nx][ny], nx, ny})
                    visited[nx][ny] = true
                }
            }
        }

        result[idx] = points
    }

    return result
}

결과 분석

위 개선 방법으로 모든 TC를 통과할 수 있었습니다!
얼만큼의 차이가 있었는지 한번 분석해보겠습니다 👀

1. Brute Force

• 모든 쿼리 (k) 만큼 모든 그리드(n * m) 에 대해서 BFS를 수행
• O( k * n * m)
• k 가 최대 10의 4승, n 과 m 이 각각 10의 5승이기 때문에 최악의 케이스엔 최소 10의 14승 번 루프를 도는 알고리즘 풀이였습니다! 😮

2. minHeap + Sorting

• 처음 queries 를 정렬하는데 필요한 시간 복잡도 k * log k (평균적인 정렬 알고리즘의 시간복잡도를 가정했어요)
• minHeap 에 모든 그리드 (n * m) 마다 경로를 삽입 (log n * m) 하는 시간 복잡도 nm log nm
• O(n * m log n * m) 이 최종 시간 복잡도가 되고 1번 방식에 비하면 얼마나 많은 루프수가 절약되는지 확인이 가능하시겠죠?!
  (10의 4승 = 10000, log 10의 5승 = 5)

추가 개선점들

혹시 2번 방식에서 heap 을 사용하는 것을 보고 최근에 풀었던 문제 가 기억나는 분은 안 계셨을까요?
heap 을 이용해서 그래프내에 최단거리를 탐색하는 다익스트라 알고리즘을 이 문제에도 적용할 수 있답니다. 주어진 값들을 그래프로 변환하고 다익스트라 알고리즘으로 최단 경로에 대한 정보를 생성. 이후에 다익스트라로 만들어진 최단거리 기록을 보고 query 값에 맞는 적절한 값을 찾는 과정으로 푼다면 조금 더 효율적으로 문제를 해결할 수 있을거에요!

다음번에도 이런 난이도가 있는 문제를 만나면 동시에 여러 알고리즘을 이용한 풀이법과 설명을 계속해서 추가해보도록 하겠습니다.

---

이번 한주의 챌린지는 DFS, BFS, 다익스트라 공유는 드리지 않았지만 Union Find 와 같은 경로 탐색류의 문제로 반복되는 한 주였습니다!
이렇게 한 장르를 분석하고 넘어가는 과정도 굉장히 즐거워서 다음 주의 챌린지도 기대가 되는데요! 그럼 여러분과 함께할 다음주 도전도 기대하겠습니다! 💪✨