Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 점프 게임 IV 풀이: BFS로 최소 점프 횟수 구하기

문제 설명

정수 배열 arr가 주어졌을 때, 우리는 처음에 인덱스 0에 위치해 있습니다. 한 번의 점프로 다음 세 가지 이동이 가능합니다.

  • i + x : 단, i + x < n (오른쪽으로 이동)
  • i - x : 단, i - x >= 0 (왼쪽으로 이동)
  • j : arr[i]와 arr[j]의 값이 같고 i != j인 임의의 인덱스로 이동

여기서 n은 배열의 크기입니다. 우리가 구해야 하는 것은 배열의 마지막 인덱스(n-1)에 도달하기 위한 최소 점프 횟수입니다.

입력 예시

입력이 다음과 같다고 가정해 보겠습니다.

{20, -5, -5, 25, 20, 5, 5, 5, 1, 25}

이때 출력은 3입니다. 인덱스 0 → 4 → 3 → 9 순서로 딱 세 번의 점프만 하면 마지막 인덱스에 도달할 수 있기 때문입니다.

  • 인덱스 0(값 20) → 인덱스 4(값 20) : 같은 값을 가진 인덱스로 점프
  • 인덱스 4 → 인덱스 3 : 한 칸 왼쪽으로 이동
  • 인덱스 3(값 25) → 인덱스 9(값 25) : 같은 값을 가진 인덱스로 점프하여 도착

풀이 접근: 너비 우선 탐색(BFS)

이 문제는 그래프 탐색 관점에서 바라보면 명확해집니다. 각 인덱스를 노드로, 이동 가능한 경로를 간선으로 생각하면 '인덱스 0에서 인덱스 n-1까지의 최단 거리'를 구하는 문제와 동일합니다. 따라서 BFS(너비 우선 탐색)를 사용하면 레벨 단위로 탐색하면서 최소 점프 횟수를 보장받을 수 있습니다.

알고리즘 단계

  1. 값을 키(key)로, 해당 값이 등장하는 인덱스들의 목록을 값(value)으로 갖는 맵 m을 정의합니다.
  2. n := arr의 크기
  3. i를 0부터 n-1까지 순회하며 m[arr[i]]의 끝에 i를 삽입합니다.
  4. 방문 집합 visited에 0을 삽입하고, 큐 q에도 0을 넣습니다.
  5. lvl := 0부터 시작하여 큐가 빌 때까지 레벨을 1씩 증가시키며 반복합니다.
    • sz := 큐의 현재 크기
    • sz가 0이 될 때까지 다음을 반복합니다.
      • curr := 큐의 맨 앞 요소를 꺼냅니다.
      • curr == n - 1이라면 lvl을 반환합니다.
      • i := curr
      • i - 1 >= 0이고 아직 방문하지 않았다면 i - 1을 큐에 넣고 방문 처리합니다.
      • i + 1 < n이고 아직 방문하지 않았다면 i + 1을 큐에 넣고 방문 처리합니다.
      • m[arr[curr]]에 담긴 모든 인덱스 j에 대해, 아직 방문하지 않았다면 큐에 넣고 방문 처리합니다.
      • 처리가 끝난 후 m에 arr[curr]가 존재하면 해당 키를 삭제합니다.
  6. 큐가 비었는데도 도달하지 못했다면 -1을 반환합니다.

핵심 최적화 포인트

주목할 부분은 특정 값에 속한 모든 인덱스를 큐에 넣은 직후 맵에서 해당 키를 삭제하는 것입니다. 같은 값이 수천 번 등장하는 배열에서는 매번 동일한 인덱스 목록을 다시 순회하게 되어 최악의 경우 O(n²) 시간이 걸릴 수 있습니다. 이미 처리한 값의 목록을 제거하면 불필요한 반복을 없애고 전체 시간 복잡도를 O(n) 수준으로 유지할 수 있습니다.

C++ 구현 예제

아래 코드를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minJumps(vector<int>& arr) {
      map<int, vector<int> > m;
      int n = arr.size();
      for (int i = 0; i < n; i++) {
         m[arr[i]].push_back(i);
      }
      set<int> visited;
      visited.insert(0);
      queue<int> q;
      q.push(0);
      for (int lvl = 0; !q.empty(); lvl++) {
         int sz = q.size();
         while (sz--) {
            int curr = q.front();
            q.pop();
            if (curr == n - 1)
            return lvl;
            int i = curr;
            if (i - 1 >= 0 && !visited.count(i - 1)) {
               q.push(i - 1);
               visited.insert(i - 1);
            }
            if (i + 1 < n && !visited.count(i + 1)) {
               q.push(i + 1);
               visited.insert(i + 1);
            }
            for (int j = 0; j < m[arr[curr]].size(); j++) {
               if (!visited.count(m[arr[curr]][j])) {
                  q.push(m[arr[curr]][j]);
                  visited.insert(m[arr[curr]][j]);
               }
            }
            if (m.count(arr[curr])) {
               m.erase(arr[curr]);
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<int> v = {20,-5,-5,25,20,5,5,5,1,25};
   cout << (ob.minJumps(v));
}

실행 결과

입력

{20,-5,-5,25,20,5,5,5,1,25}

출력

3

마무리

점프 게임 IV는 BFS의 레벨 단위 탐색과 맵 자료구조를 결합해 풀어야 하는 대표적인 그래프 최단 경로 문제입니다. 인접 이동(i ± 1)과 동일 값 점프(arr[j] == arr[i])라는 두 종류의 간선을 모두 고려하고, 방문 처리와 맵 삭제 최적화를 함께 적용하면 어떤 입력에 대해서도 효율적으로 최소 점프 횟수를 구할 수 있습니다.