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

C++ 고유 경로 II – 장애물이 있는 격자에서의 경로 개수 구하기

n×m 크기의 격자(그리드)가 있고, 로봇이 왼쪽 상단 모서리에 위치해 있다고 가정해 보겠습니다. 로봇은 임의의 시점에서 아래쪽 또는 오른쪽으로만 이동할 수 있습니다. 로봇의 목표는 격자의 오른쪽 하단 모서리(아래 표에서 'END'로 표시된 위치)에 도달하는 것입니다.

격자의 일부 칸은 장애물로 표시되어 있으며, 로봇은 해당 칸을 지나갈 수 없습니다. 따라서 우리는 시작 위치에서 도착 위치까지 갈 수 있는 고유한 경로의 총 개수를 구해야 합니다.

예를 들어 격자가 [[0,0,0],[0,1,0],[0,0,0]]과 같다면, 격자는 아래와 같이 표현됩니다.

Robo


Obs


END

이 경우 출력값은 2입니다. 즉, 시작 위치에서 도착 위치까지 도달할 수 있는 서로 다른 경로는 총 2가지이며, 각 경로는 다음과 같습니다.

  1. 오른쪽 → 오른쪽 → 아래 → 아래
  2. 아래 → 아래 → 오른쪽 → 오른쪽

동적 계획법(DP)을 활용한 접근 방식

이 문제는 동적 계획법(Dynamic Programming)을 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 칸에 도달할 수 있는 경로의 수를 저장하고, 현재 칸의 경로 수는 위쪽 칸과 왼쪽 칸의 경로 수의 합이라는 점을 이용하는 것입니다. 단, 장애물이 있는 칸의 경로 수는 항상 0이 됩니다.

알고리즘 단계

  • a := 행의 개수, b := 열의 개수로 설정합니다.
  • grid[a-1][b-1](도착 지점)이 장애물이면 0을 반환합니다.
  • a×b 크기의 DP 테이블을 생성합니다.
  • i := b-1부터 0까지 감소시키며 반복합니다.
    • grid[a-1][i]가 장애물이면 반복을 중단(break)하고, 그렇지 않으면 DP[a-1][i] := 1로 설정합니다. (마지막 행 초기화)
  • i := a-1부터 0까지 감소시키며 반복합니다.
    • grid[i][b-1]이 장애물이면 반복을 중단(break)하고, 그렇지 않으면 DP[i][b-1] := 1로 설정합니다. (마지막 열 초기화)
  • i := a-2부터 0까지, j := b-2부터 0까지 이중 반복문을 실행합니다.
    • grid[i][j]가 0(장애물 없음)이면 DP[i][j] := DP[i+1][j] + DP[i][j+1], 그렇지 않으면 DP[i][j] := 0으로 설정합니다.
  • 최종적으로 DP[0, 0]을 반환합니다.

C++ 구현 예제

다음 구현 코드를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
      int a = obstacleGrid.size();
      int b = obstacleGrid[0].size();
         if(!a || !b) return 0;
      if(obstacleGrid[a - 1][b - 1])return 0;
      vector < vector <lli> > dp(a, vector <lli>(b));
      for(int i = b - 1; i >= 0; i--)if(obstacleGrid[a-1][i]) break; else dp[a-1][i] = 1;
      for(int i = a - 1; i >= 0; i--)if(obstacleGrid[i][b - 1]) break; else dp[i][b-1] = 1 ;
      for(int i = a-2; i >= 0; i--){
         for(int j = b-2 ; j >= 0; j--)dp[i][j] = !obstacleGrid[i][j]? dp[i+1][j] + dp[i][j+1] : 0;
      }
      return dp[0][0];
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,0,0},{0,1,0},{0,0,0}};
   cout << ob.uniquePathsWithObstacles(v);
}

입력

[[0,0,0],[0,1,0],[0,0,0]]

출력

2

정리

이 알고리즘은 시간 복잡도 O(n×m), 공간 복잡도 O(n×m)으로 동작합니다. 마지막 행과 열을 먼저 초기화한 뒤, 나머지 칸들을 역순으로 순회하면서 위쪽 칸과 오른쪽 칸의 값을 더하는 방식으로 각 칸까지의 고유한 경로 수를 계산합니다. 장애물이 있는 칸은 경로 수를 0으로 처리하여 경로 탐색에서 자연스럽게 제외됩니다.