Skip to main content

작성일 : 2024.12.01

등굣길 문제

문제 설명​

격자 모양의 지도에서 집(1,1)에서 학교(m,n)까지 가는 최단경로의 개수를 구하는 문제입니다. 다음과 같은 조건이 있습니다:

  • 오른쪽과 아래쪽으로만 이동 가능
  • 물에 잠긴 지역은 통과할 수 없음
  • 정답을 1,000,000,007로 나눈 나머지를 반환

등굣길 예시

제한 조건​

  1. 격자 크기 (m, n)

    • 범위: 1 ≤ m, n ≤ 100
    • m과 n이 모두 1인 경우는 없음

  2. 물에 잠긴 지역 (puddles)

    • 개수: 0 ≤ puddles ≤ 10
    • 집과 학교는 물에 잠기지 않음

해결 코드​

function solution(m, n, puddles) {
  var answer = 0;
  let graph = Array.from(Array(n + 1), () => Array(m + 1).fill(0));
  graph[0][0] = 1;

  // 물웅덩이 표시
  for (let p = 0; p < puddles.length; p++) {
    graph[puddles[p][1] - 1][puddles[p][0] - 1] = -1;
  }

  // 경로 계산
  for (let i = 0; i < n; i++) {
    for (let k = 0; k < m; k++) {
      if (graph[i][k] == -1) continue;

      if (i > 0 && graph[i - 1][k] != -1) {
        graph[i][k] = graph[i][k] + graph[i - 1][k];
      }

      if (k > 0 && graph[i][k - 1] != -1) {
        graph[i][k] = graph[i][k] + graph[i][k - 1];
      }
      graph[i][k] = graph[i][k] % 1000000007;
    }
  }
  return graph[n - 1][m - 1];
}

알고리즘 설명​

  1. DP 배열 초기화
let graph = Array.from(Array(n + 1), () => Array(m + 1).fill(0));
graph[0][0] = 1; // 시작점
  1. 물웅덩이 표시
for (let p = 0; p < puddles.length; p++) {
  graph[puddles[p][1] - 1][puddles[p][0] - 1] = -1;
}
  1. 최단경로 개수 계산
// 현재 위치 = 위쪽 경로 수 + 왼쪽 경로 수
if (i > 0 && graph[i - 1][k] != -1) {
  graph[i][k] += graph[i - 1][k];
}
if (k > 0 && graph[i][k - 1] != -1) {
  graph[i][k] += graph[i][k - 1];
}

동적 계획법 (DP) 설계​

  1. 상태 정의

    • graph[i][j]: (i,j)까지 도달하는 최단경로의 수

  2. 점화식

    graph[i][j] = graph[i-1][j] + graph[i][j-1]
    (단, 물웅덩이가 아닌 경우)

  3. 초기값

    • graph[0][0] = 1
    • 물웅덩이 = -1

구현 포인트​

  1. 모듈러 연산
graph[i][k] = graph[i][k] % 1000000007;
  1. 경계 조건 처리
if(i>0 && graph[i-1][k] != -1)  // 위쪽 경로 확인
if(k>0 && graph[i][k-1] != -1)  // 왼쪽 경로 확인

시간 복잡도​

  • O(m * n): 격자의 모든 칸을 한 번씩 방문

공간 복잡도​

  • O(m * n): 2차원 DP 배열 사용

주의사항​

  1. 좌표계 주의 (1-based → 0-based)
  2. 오버플로우 방지를 위한 모듈러 연산
  3. 물웅덩이 위치의 정확한 처리