역추적 알고리즘(Backtracking Algorithm)

 

당신은 로봇이 움직이는 2D 그리드 상에서 최단 경로를 찾는 알고리즘을 개발하고 있습니다. 로봇은 시작 지점 (0, 0)에서 목표 지점 (m, n)으로 이동해야 합니다. 로봇은 오른쪽 방향으로만 움직일 수 있으며, 한 번에 한 칸씩 이동할 수 있습니다. 그리드 상의 각 셀은 장애물일 수도 있어 로봇은 장애물을 피해야 합니다.

이제 로봇의 최단 경로를 찾는 역추적 알고리즘을 구현해야 합니다. 주어진 dp 테이블과 그리드 정보를 이용하여 시작 지점부터 목표 지점까지의 최단 경로를 찾는 함수 traceShortestPath(dp, grid)를 작성해주세요. 함수는 최단 경로에 해당하는 좌표들의 배열을 반환해야 합니다.

함수의 입력:

• dp: 로봇의 최단 경로를 저장한 DP 테이블 (2D 배열)
• grid: 장애물 정보를 담은 그리드 (2D 배열)

함수의 출력:

• 최단 경로에 해당하는 좌표들로 이루어진 배열

주의사항:

• dp 테이블은 로봇의 최단 경로를 역추적하기 위해 사용됩니다. 이 테이블에는 각 셀까지의 최단 경로의 길이가 저장되어 있어야 합니다.
• 그리드의 각 셀은 장애물 여부를 나타내는 값으로, 0은 장애물이 없음을 의미하고, 1은 장애물이 있는 것을 의미합니다.
• 최단 경로가 존재하지 않을 경우, 빈 배열을 반환해야 합니다.
• 로봇은 오른쪽 방향으로만 이동하므로, 최단 경로는 항상 왼쪽 위에서 오른쪽 아래로 이동하는 경로입니다.

function traceShortestPath(dp, grid) {
  const m = dp.length;
  const n = dp[0].length;

  // 시작 지점과 목표 지점의 좌표
  const start = [0, 0];
  const target = [m - 1, n - 1];

  // 장애물이 있는 좌표를 저장할 Set
  const obstacles = new Set();
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) {
        obstacles.add(`${i},${j}`);
      }
    }
  }

  // 최단 경로를 저장할 배열
  const path = [start];

  let [x, y] = start;

  while (x !== target[0] || y !== target[1]) {
    let minCost = Infinity;
    let nextX = x;
    let nextY = y;

    // 오른쪽으로 이동하는 경우
    if (y + 1 < n && dp[x][y + 1] < minCost && !obstacles.has(`${x},${y + 1}`)) {
      minCost = dp[x][y + 1];
      nextX = x;
      nextY = y + 1;
    }

    // 아래로 이동하는 경우
    if (x + 1 < m && dp[x + 1][y] < minCost && !obstacles.has(`${x + 1},${y}`)) {
      minCost = dp[x + 1][y];
      nextX = x + 1;
      nextY = y;
    }

    // 다음 좌표로 이동
    x = nextX;
    y = nextY;
    path.push([x, y]);
  }

  return path;
}

const dp = [
  [0, 1, 2],
  [0, 2, 4],
  [0, 3, 6]
];

const grid = [
  [0, 0, 0],
  [0, 1, 0],
  [0, 0, 0]
];

const shortestPath = traceShortestPath(dp, grid);
console.log(shortestPath); // [[0, 0], [1, 0], [2, 0], [2, 1], [2, 2]]

 

위의 예시에서는 주어진 DP 테이블과 그리드 정보를 바탕으로 로봇의 최단 경로를 역추적하여 [[0, 0], [1, 0], [2, 0], [2, 1], [2, 2]]를 반환합니다. 이는 시작 지점 (0, 0)에서 목표 지점 (2, 2)까지의 최단 경로를 나타냅니다.